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>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,d,mod,C[110][110],dp[110][110][110][2],trans[110][110],po[110][110];
inline int kpow(int a,int b)
{
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)s=1ll*s*a%mod;
	return s;
}
int main()
{
	scanf("%d %d %d %d",&n,&m,&d,&mod);
	for(int i=0;i<=n||i<=m||i<=d;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)(C[i][j]=C[i-1][j-1]+C[i-1][j])>=mod?C[i][j]-=mod:0;
		po[i][0]=1;
		for(int j=1;j<=n||j<=m||j<=d;++j)po[i][j]=1ll*po[i][j-1]*i%mod;
	}
	dp[1][0][0][0]=1;
	for(int k=1;k<=d;++k)
	{
		for(int j=0;j<=m;++j)
		{
			trans[j][0]=1;
			int tmp=1ll*(po[k][m-j]+mod-po[k-1][m-j])*po[d-k+1][j]%mod;
			for(int i=1;i<=n;++i)trans[j][i]=1ll*trans[j][i-1]*tmp%mod;
		}
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				if(dp[k][i][j][0])
					for(int x=0;x+i<=n;++x)dp[k][i+x][j][1]=(dp[k][i+x][j][1]+1ll*C[n-i][x]*dp[k][i][j][0]%mod*trans[j][x])%mod;
		for(int i=0;i<=n;++i)
		{
			trans[i][0]=1;
			int tmp=1ll*(po[d-k+1][i]+mod-po[d-k][i])*po[k][n-i]%mod;
			for(int j=1;j<=m;++j)trans[i][j]=1ll*trans[i][j-1]*tmp%mod;
		}
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				if(dp[k][i][j][1])
					for(int x=0;x+j<=m;++x)dp[k+1][i][j+x][0]=(dp[k+1][i][j+x][0]+1ll*C[m-j][x]*dp[k][i][j][1]%mod*trans[i][x])%mod;
	}
	printf("%d",dp[d+1][n][m][0]);
	return 0;
}