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;

int pw[105][105],C[105][105];
int dp[2][105][105];

int main()
{
	int n,m,k,d;
	scanf("%d%d%d%d",&n,&m,&k,&d);
	C[0][0] = 1;
	for(int i = 1;i <= 100; ++ i)
	{
		C[i][0] = 1;
		pw[i][0] = 1;
		for(int j = 1;j <= 100; ++ j)
			pw[i][j] = pw[i][j - 1] * 1ll * i % d,
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % d;
	}
	int cur = 1,nxt = 0;
	dp[0][0][0] = 1;
	for(int i = 1;i <= k; ++ i)
	{
		cur ^= 1; nxt ^= 1; memset(dp[nxt],0,sizeof(dp[nxt]));
		for(int j = 0;j <= n; ++ j)
			for(int l = 0;l <= m; ++ l)
			{
				int tm = pw[k - i + 1][l] * 1ll * pw[i][m - l] % d;
				for(int p = 0,x = dp[cur][j][l];j + p <= n; ++ p,x = x * 1ll * tm % d)
					dp[nxt][j + p][l] = (dp[nxt][j + p][l] + x * 1ll * C[n - j][p]) % d;
			}
		cur ^= 1; nxt ^= 1; memset(dp[nxt],0,sizeof(dp[nxt]));
		for(int j = 0;j <= n; ++ j)
			for(int l = 0;l <= m; ++ l)
			{
				int tm = pw[k - i + 1][j] * 1ll * pw[i][n - j] % d;
				for(int p = 0,x = dp[cur][j][l];l + p <= m; ++ p,x = x * 1ll * tm % d)
					dp[nxt][j][l + p] = (dp[nxt][j][l + p] + x * 1ll * C[m - l][p]) % d;
			}
		cur ^= 1; nxt ^= 1; memset(dp[nxt],0,sizeof(dp[nxt]));
		for(int j = 0;j <= n; ++ j)
			for(int l = 0;l <= m; ++ l)
			{
				int tm = pw[k - i][l] * 1ll * pw[i][m - l] % d * (d - 1) % d;
				for(int p = 0,x = dp[cur][j][l];j + p <= n; ++ p,x = x * 1ll * tm % d)
					dp[nxt][j + p][l] = (dp[nxt][j + p][l] + x * 1ll * C[n - j][p]) % d;
			}
		cur ^= 1; nxt ^= 1; memset(dp[nxt],0,sizeof(dp[nxt]));
		for(int j = 0;j <= n; ++ j)
			for(int l = 0;l <= m; ++ l)
			{
				int tm = (d - 1) * 1ll * pw[k - i][j] % d * pw[i][n - j] % d;
				for(int p = 0,x = dp[cur][j][l];l + p <= m; ++ p,x = x * 1ll * tm % d)
					dp[nxt][j][l + p] = (dp[nxt][j][l + p] + x * 1ll * C[m - l][p]) % d;
			}
	}
	printf("%d\n",dp[nxt][n][m]);
}