F - Min Product Sum /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 2000

問題文

NM 列のマス目の全てのマスに 1 以上 K 以下の整数を書き込む方法 K^{NM} 通りすべてに対して以下の値を求め、 それらすべての総和を D で割ったあまりを求めてください。

  • NM 個の各マスに対し、それと同じ行あるいは同じ列のマス (自分自身を含む) に書かれた整数の最小値を求め、それら NM 個すべての積を取って得られる値

制約

  • 1 \leq N,M,K \leq 100
  • 10^8 \leq D \leq 10^9
  • N,M,K,D は整数である
  • D は素数である

入力

入力は以下の形式で標準入力から与えられる。

N M K D

出力

K^{NM} 個の値の総和を D で割ったあまりを出力せよ。


入力例 1

2 2 2 998244353

出力例 1

35

NM 個の値の積が 16 になる書き込み方が 1 通り、2 になる書き込み方が 4 通り、1 になる書き込み方が 11 通りあります。


入力例 2

2 3 4 998244353

出力例 2

127090

入力例 3

31 41 59 998244353

出力例 3

827794103

Score : 2000 points

Problem Statement

For each of the K^{NM} ways to write an integer between 1 and K (inclusive) in every square in a square grid with N rows and M columns, find the value defined below, then compute the sum of all those K^{NM} values, modulo D.

  • For each of the NM squares, find the minimum among the N+M-1 integers written in the square's row or the square's column. The value defined for the grid is the product of all these NM values.

Constraints

  • 1 \leq N,M,K \leq 100
  • 10^8 \leq D \leq 10^9
  • N,M,K, and D are integers.
  • D is prime.

Input

Input is given from Standard Input in the following format:

N M K D

Output

Print the sum of the K^{NM} values, modulo D.


Sample Input 1

2 2 2 998244353

Sample Output 1

35

We have 1 way to write integers such that the product of the NM values is 16, 4 ways such that the product is 2, and 11 ways such that the product is 1.


Sample Input 2

2 3 4 998244353

Sample Output 2

127090

Sample Input 3

31 41 59 998244353

Sample Output 3

827794103