問題文

$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