题目描述

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

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

输入格式

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

$N$ $M$ $K$ $D$

输出格式

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

题目大意

• 有一个大小为 $N \times M$ 的矩阵。矩阵中每个数的取值都是 $[1, K]$。
• 对于一个矩阵，定义函数 $f(x,y)$ 为：第 $x$ 行和第 $y$ 列的一共 $N + M - 1$ 个数中的最小值。
• 对于一个矩阵，定义其权值为 $\prod_{x=1}^{N}\prod_{y=1}^{M}f(x,y)$。
• 你需要求出，对于所有 $K^{NM}$ 种矩阵，每个矩阵的权值和对 $D$ 取模的结果。
• $1 \leq N, M, K \leq 100$，$10^8 \leq D \leq 10^9$，保证 $D$ 为质数。

2 2 2 998244353

35

2 3 4 998244353

127090

31 41 59 998244353

827794103

提示

制約

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

Sample Explanation 1

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