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<cstdio>
const int MAXN = 100;
int D;
inline int add(int a, int b) {return (a + b)%D;}
inline int mul(int a, int b) {return 1LL*a*b%D;}
inline int sub(int a, int b) {return add(a,D-b);}
int pow_mod(int b, int p) {
	int ret = 1;
	while( p ) {
		if( p & 1 ) ret = mul(ret, b);
		b = mul(b, b);
		p >>= 1;
	}
	return ret;
}
int comb[MAXN + 5][MAXN + 5];
int trans1[MAXN + 5][MAXN + 5][MAXN + 5];
int trans2[MAXN + 5][MAXN + 5][MAXN + 5];
int f[MAXN + 5][MAXN + 5][MAXN + 5];
int g[MAXN + 5][MAXN + 5][MAXN + 5];
int N, M, K;
void init() {
	for(int i=0;i<=MAXN;i++) {
		comb[i][0] = 1;
		for(int j=1;j<=i;j++)
			comb[i][j] = add(comb[i-1][j], comb[i-1][j-1]);
	}
	for(int i=1;i<=K;i++) {
		for(int k=0;k<=M;k++) {
			trans1[i][k][0] = 1;
			if( k == M ) trans1[i][k][1] = 0;
			else trans1[i][k][1] = mul(pow_mod(K-i+1, k), sub(pow_mod(i, M-k), pow_mod(i-1, M-k)));
			for(int p=2;p<=N;p++)
				trans1[i][k][p] = mul(trans1[i][k][p-1], trans1[i][k][1]);
		}
	}
	for(int i=1;i<=K;i++) {
		for(int j=0;j<=N;j++) {
			trans2[i][j][0] = 1;
			if( j == 0 ) trans2[i][j][1] = 0;
			else trans2[i][j][1] = mul(pow_mod(i, N-j), sub(pow_mod(K-i+1, j), pow_mod(K-i, j)));
			for(int q=2;q<=M;q++)
				trans2[i][j][q] = mul(trans2[i][j][q-1], trans2[i][j][1]);
		}
	}
}
int main() {
	scanf("%d%d%d%d", &N, &M, &K, &D), init();
	f[0][0][0] = 1;
	for(int i=1;i<=K;i++) {
		for(int j=0;j<=N;j++) {
			for(int k=0;k<=M;k++) {
				for(int p=0;j+p<=N;p++) {
					g[j+p][k][i] = add(g[j+p][k][i], mul(comb[N-j][p], mul(trans1[i][k][p], f[j][k][i-1])));
// g[j+p][k][i] = g[j+p][k][i] + ((K-i+1)^k * (i^(M-k) - (i-1)^(M-k))^p * f[j][k][i-1]
				}
			}
		}
		for(int j=0;j<=N;j++) {
			for(int k=0;k<=M;k++) {
				for(int q=0;k+q<=M;q++) {
					f[j][k+q][i] = add(f[j][k+q][i], mul(comb[M-k][q], mul(trans2[i][j][q], g[j][k][i])));
// f[j][k+q][i] = f[j][k+q][i] + (i^(N-j) * ((K-i+1)^j - (K-i)^j)^q * g[j][k][i]
				}
			}
		}
	}
	printf("%d\n", f[N][M][K]);
}