/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 2000 点
問題文
N 行 M 列のマス目の全てのマスに 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