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<cmath>
#include<algorithm>
#define maxn 105
#define ll long long 
using namespace std;

int n,m,c,mo,i,j,k;
ll f[2][maxn][maxn];
ll mul[maxn][maxn*maxn],C[maxn][maxn];

ll ksm(ll x,ll y){
	ll s=1;
	for(;y;y/=2,x=x*x%mo) if (y&1)
		s=s*x%mo;
	return s;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&c,&mo);
	for(mul[0][0]=1,i=1;i<=c;i++){
		mul[i][0]=1;
		for(j=1;j<=n*m;j++) mul[i][j]=mul[i][j-1]*i%mo;
	}
	for(C[0][0]=1,i=1;i<=max(n,m);i++) for(C[i][0]=1,j=1;j<=i;j++)
		C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
	int p=0,q=1;
	for(int x=1;x<=c;x++){
		p^=1,q^=1; memset(f[p],0,sizeof(f[p]));
		for(i=0;i<=max(n,m);i++) f[q][0][i]=f[q][i][0]=0; f[q][0][0]=1;
		for(i=n;i>=0;i--) for(j=m;j>=0;j--) if (f[q][i][j]) for(k=0;k<=n-i;k++)
			(f[p][i+k][j]+=f[q][i][j]*mul[x][(m-j)*k]%mo*mul[c-x+1][j*k]%mo*C[i+k][k])%=mo;
		p^=1,q^=1; memset(f[p],0,sizeof(f[p]));
		for(i=n;i>=0;i--) for(j=m;j>=0;j--) if (f[q][i][j]) for(k=0;k<=m-j;k++)
			(f[p][i][j+k]+=f[q][i][j]*mul[x][(n-i)*k]%mo*mul[c-x+1][i*k]%mo*C[j+k][k])%=mo;
		p^=1,q^=1; memset(f[p],0,sizeof(f[p]));
		for(i=n;i>=0;i--) for(j=m;j>=0;j--) if (f[q][i][j]) for(k=0;k<=n-i;k++)
			(f[p][i+k][j]+=f[q][i][j]*mul[x][(m-j)*k]%mo*mul[c-x][j*k]%mo*C[i+k][k]*((k&1)?-1:1))%=mo;
		p^=1,q^=1; memset(f[p],0,sizeof(f[p]));
		for(i=n;i>=0;i--) for(j=m;j>=0;j--) if (f[q][i][j]) for(k=0;k<=m-j;k++)
			(f[p][i][j+k]+=f[q][i][j]*mul[x][(n-i)*k]%mo*mul[c-x][i*k]%mo*C[j+k][k]*((k&1)?-1:1))%=mo;
	}
	printf("%lld\n",(f[p][n][m]%mo+mo)%mo);
}