[AGC039F] Min Product Sum

- 有一个大小为 $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$ 为质数。

[problemUrl]: https://atcoder.jp/contests/agc039/tasks/agc039_f $ N $ 行 $ M $ 列のマス目の全てのマスに $ 1 $ 以上 $ K $ 以下の整数を書き込む方法 $ K^{NM} $ 通りすべてに対して以下の値を求め、 それらすべての総和を $ D $ で割ったあまりを求めてください。 - $ NM $ 個の各マスに対し、それと同じ行あるいは同じ列のマス (自分自身を含む) に書かれた整数の最小値を求め、それら $ NM $ 個すべての積を取って得られる値

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ D $

$ K^{NM} $ 個の値の総和を $ 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 $ 通りあります。