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:
//NMD WSM
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
int mod;
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
int g[101][101],C[101][101],CC[101][101],pw[101][10086],f[2][101][101];
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int n=gi(),m=gi(),k=gi();mod=gi();
	C[0][0]=1;
	pw[0][0]=1;
	for(int i=1;i<=100;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		pw[i][0]=1;
		for(int j=1;j<=10000;++j)pw[i][j]=1ll*pw[i][j-1]*i%mod;
	}
	for(int i=0;i<=100;++i)
		for(int j=0;j<=100;++j)
			CC[i][j]=C[j][i];
	f[0][0][0]=1;
	int t=0;
	for(int o=1;o<=k;++o){
		memset(f[!t],0,101*101*4);
		for(int j=0;j<=m;++j)for(int i=0;i<=n;++i)g[j][i]=1ll*pw[o][i*(m-j)]*pw[k-o+1][i*j]%mod;
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j){
				int w=f[t][i][j];if(!w)continue;
				int*CCC=CC[i]+i,*shit=f[!t][j]+i;
				for(int ni=0;ni<=n-i;++ni)inc(shit[ni],1ll*w*CCC[ni]%mod*g[j][ni]%mod);
			}
		t^=1;memset(f[!t],0,101*101*4);
		for(int i=0;i<=100;++i)for(int j=i+1;j<=100;++j)std::swap(f[t][i][j],f[t][j][i]);
		for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)g[i][j]=1ll*pw[o][j*(n-i)]*pw[k-o+1][i*j]%mod;
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j){
				int*CCC=CC[j]+j,*shit=f[!t][i]+j;
				int w=f[t][i][j];if(!w)continue;
				for(int nj=0;nj<=m-j;++nj)inc(shit[nj],1ll*w*CCC[nj]%mod*g[i][nj]%mod);
			}
		t^=1;memset(f[!t],0,101*101*4);
		for(int j=0;j<=m;++j)for(int i=0,M=1;i<=n;++i,M=mod-M)g[j][i]=1ll*pw[o][i*(m-j)]*pw[k-o][i*j]%mod*M%mod;
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j){
				int w=f[t][i][j];if(!w)continue;
				int*CCC=CC[i]+i,*shit=f[!t][j]+i;
				for(int ni=0;ni<=n-i;++ni)inc(shit[ni],1ll*w*CCC[ni]%mod*g[j][ni]%mod);
			}
		t^=1;memset(f[!t],0,101*101*4);
		for(int i=0;i<=100;++i)for(int j=i+1;j<=100;++j)std::swap(f[t][i][j],f[t][j][i]);
		for(int i=0;i<=n;++i)for(int j=0,M=1;j<=m;++j,M=mod-M)g[i][j]=1ll*pw[o][j*(n-i)]*pw[k-o][i*j]%mod*M%mod;
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j){
				int*CCC=CC[j]+j,*shit=f[!t][i]+j;
				int w=f[t][i][j];if(!w)continue;
				for(int nj=0;nj<=m-j;++nj)inc(shit[nj],1ll*w*CCC[nj]%mod*g[i][nj]%mod);
			}
		t^=1;
	}
	printf("%d\n",f[t][n][m]);
	return 0;
}