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>
const int N=105;
int n,m,K,i,j,k,l,mo,mi[N][N*N],f[2][N][N],h[N][N],fac[N],inv[N],vf[N],nw,ans,w[N][N];
int main(){
	scanf("%d%d%d%d",&n,&m,&K,&mo);
	for(i=*fac=*vf=1;i<N;++i)
		fac[i]=1ll*fac[i-1]*i%mo,
		inv[i]=i==1?1:1ll*(mo-mo/i)*inv[mo%i]%mo,
		vf[i]=1ll*vf[i-1]*inv[i]%mo;
	for(i=0;i<N;++i)for(j=*mi[i]=1;j<N*N;++j)mi[i][j]=1ll*mi[i][j-1]*i%mo;
	f[0][0][0]=1;
	for(i=K;i;--i){
/*
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(k=0;k<=m;++k)for(l=0;l<=n;++l)w[k][l]=1ll*mi[K-i+1][l*(m-k)]*vf[l]%mo*mi[i][l*k]%mo;
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;j+l<=n;++l)
			f[nw][j+l][k]=(f[nw][j+l][k]+1ll*w[k][l]*f[!nw][j][k])%mo;
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(l=0;l<=m;++l)w[j][l]=1ll*mi[K-i+1][l*(n-j)]*vf[l]%mo*mi[i][l*j]%mo;
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;l+k<=m;++l)
			f[nw][j][l+k]=(f[nw][j][l+k]+1ll*w[j][l]*f[!nw][j][k])%mo;
*/
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;j+l<=n;++l)
			f[nw][j+l][k]=(f[nw][j+l][k]+1ll*mi[K-i+1][l*(m-k)]*vf[l]%mo*mi[i][l*k]%mo*f[!nw][j][k])%mo;
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;l+k<=m;++l)
			f[nw][j][l+k]=(f[nw][j][l+k]+1ll*mi[K-i+1][l*(n-j)]*vf[l]%mo*mi[i][l*j]%mo*f[!nw][j][k])%mo;
/*
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;j+l<=n;++l)
			f[nw][j+l][k]=(f[nw][j+l][k]+1ll*mi[K-i+1][l*(m-k)]*(l&1?mo-vf[l]:vf[l])%mo*mi[i-1][l*k]%mo*f[!nw][j][k])%mo;
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;l+k<=m;++l)
			f[nw][j][l+k]=(f[nw][j][l+k]+1ll*mi[K-i+1][l*(n-j)]*(l&1?mo-vf[l]:vf[l])%mo*mi[i-1][l*j]%mo*f[!nw][j][k])%mo;
*/
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(k=0;k<=m;++k)for(l=0;l<=n;++l)w[k][l]=1ll*mi[K-i+1][l*(m-k)]*(l&1?mo-vf[l]:vf[l])%mo*mi[i-1][l*k]%mo;
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;j+l<=n;++l)
			f[nw][j+l][k]=(f[nw][j+l][k]+1ll*w[k][l]*f[!nw][j][k])%mo;
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(l=0;l<=m;++l)w[j][l]=1ll*mi[K-i+1][l*(n-j)]*(l&1?mo-vf[l]:vf[l])%mo*mi[i-1][l*j]%mo;
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;l+k<=m;++l)
			f[nw][j][l+k]=(f[nw][j][l+k]+1ll*w[j][l]*f[!nw][j][k])%mo;
/*
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;j+l<=n;++l)
			f[nw][j+l][k]=(f[nw][j+l][k]+1ll*mi[K-i+1][l*(m-k)]*(l&1?mo-vf[l]:vf[l])%mo*mi[i-1][l*k]%mo*f[!nw][j][k])%mo;
		nw^=1;memset(f[nw],0,sizeof f[nw]);
		for(j=0;j<=n;++j)for(k=0;k<=m;++k)for(l=0;l+k<=m;++l)
			f[nw][j][l+k]=(f[nw][j][l+k]+1ll*mi[K-i+1][l*(n-j)]*(l&1?mo-vf[l]:vf[l])%mo*mi[i-1][l*j]%mo*f[!nw][j][k])%mo;
*/
	}
	ans=f[nw][n][m];
	ans=1ll*fac[n]*fac[m]%mo*ans%mo;
	printf("%d\n",ans);
	return 0;
}