Problem: 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.

Examples

Input

2 2 2 998244353


Output

35


Input

2 3 4 998244353


Output

127090


Input

31 41 59 998244353


Output

827794103

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;

int n, m, K, MOD;

inline int inc(int a, int b) { return (a + b >= MOD) ? (a + b - MOD) : (a + b); }
inline int dec(int a, int b) { return (a >= b) ? (a - b) : (a + MOD - b); }
inline int mul(int a, int b) { return 1LL * a * b % MOD; }

inline void updata(int &x, int y) { x = inc(x,y); }

inline int power(int x, int k) {
	int tmp = 1;
	while(k) {
		if(k & 1) tmp = mul(tmp,x);
		x = mul(x,x);
		k >>= 1;
	}
	return tmp;
}

int xs[2][maxn][maxn][maxn], dp[maxn][maxn][maxn][2], fac[maxn], ifac[maxn], C[maxn][maxn];

//inline int C(int n, int m) {
//	if(n < 0 || m < 0 || n < m) return 0;
//	return mul(fac[n],mul(ifac[m],ifac[n - m]));
//}

int main() {
	scanf("%d%d%d%d", &n, &m, &K, &MOD);
	fac[0] = ifac[0] = 1;
	for(int i = 1;i <= 100;i ++) fac[i] = mul(fac[i - 1],i);
	ifac[100] = power(fac[100],MOD - 2);
	for(int i = 99;i >= 1;i --) ifac[i] = mul(ifac[i + 1],i + 1);
	C[0][0] = 1;
	for(int i = 1;i <= 100;i ++) {
		C[i][0] = 1;
		for(int j = 1;j <= 100;j ++) C[i][j] = inc(C[i - 1][j],C[i - 1][j - 1]);
	}
	for(int i = 1;i <= K;i ++) {
		for(int j = 0;j <= m;j ++) {
			int now = mul(dec(power(i,m - j),power(i - 1,m - j)),power(K - i + 1,j)), tmp = 1;
			for(int k = 0;k <= n;k ++) {
				xs[0][i][j][k] = tmp;
				tmp = mul(tmp,now);
			}
		}
	}
	for(int i = 1;i <= K;i ++) {
		for(int j = 0;j <= n;j ++) {
			int now = mul(dec(power(K - i + 1,j),power(K - i,j)),power(i,n - j)), tmp = 1;
			for(int k = 0;k <= m;k ++) {
				xs[1][i][j][k] = tmp;
				tmp = mul(tmp,now);
			}
		}
	}
	dp[1][0][0][0] = 1;
	for(int k = 1;k <= K;k ++) {
		for(int i = 0;i <= n;i ++) {
			for(int j = 0;j <= m;j ++) {
        for(int l = 0;l + i <= n;l ++) {
					int now = mul(xs[0][k][j][l],C[n - i][l]);
					updata(dp[k][i + l][j][1],mul(dp[k][i][j][0],now));
				}
				for(int l = 0;l + j <= m;l ++) {
					int now = mul(xs[1][k][i][l],C[m - j][l]);
					updata(dp[k + 1][i][j + l][0],mul(dp[k][i][j][1],now));
				}
			}
		}
	}
	int Ans = dp[K + 1][n][m][0];
	printf("%d\n", Ans);
	return 0;
}