配点 : $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$ で割ったあまりを出力せよ。

2 2 2 998244353

35

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

2 3 4 998244353

127090

31 41 59 998244353

827794103