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 mod;
int ksm(int b,int n){
	int res=1;
	while(n){
		if(n&1) res=1ll*res*b%mod;
		b=1ll*b*b%mod; n>>=1;
	}
	return res;
}
int f[2][105][105],pw[105][10005],C[105][105];
void init(int n){
	for(int i=0;i<=n;++i){
		pw[i][0]=1;
		for(int j=1;j<=n*n;++j)
			pw[i][j]=1ll*pw[i][j-1]*i%mod;
	}
	C[0][0]=1;
	for(int i=1;i<=n;++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;
	}
}
void add(int &x,int y){
	x=(x+y)%mod;
}
signed main(){
	int n,m,K;
	cin>>n>>m>>K>>mod;
	init(100);
	f[0][0][0]=1;int u=0;
	for(int k=1;k<=K;++k){
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				if(f[u][i][j]){
					int now=f[u][i][j],Pw=1ll*pw[k][m-j]*pw[K-k+1][j]%mod;
					for(int a=0;i+a<=n;++a)
						add(f[u^1][i+a][j],1ll*now*C[n-i][a]%mod),now=1ll*now*Pw%mod;	
				}
		u^=1;
		memset(f[u^1],0,sizeof(f[u^1]));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				if(f[u][i][j]){
					int now=f[u][i][j],Pw=1ll*pw[k][n-i]*pw[K-k+1][i]%mod;
					for(int b=0;j+b<=m;++b)
						add(f[u^1][i][j+b],1ll*now*C[m-j][b]%mod),now=1ll*now*Pw%mod;
				}
		u^=1;
		memset(f[u^1],0,sizeof(f[u^1]));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				if(f[u][i][j]){
					int tmp,now=f[u][i][j],Pw=1ll*pw[k][m-j]*pw[K-k][j]%mod;
					for(int a=0;i+a<=n;++a)
						tmp=1ll*now*C[n-i][a]%mod,
						add(f[u^1][i+a][j],(a&1?mod-tmp:tmp)),
						now=1ll*now*Pw%mod;							
				}
		u^=1;
		memset(f[u^1],0,sizeof(f[u^1]));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				if(f[u][i][j]){
					int tmp,now=f[u][i][j],Pw=1ll*pw[k][n-i]*pw[K-k][i]%mod;
					for(int b=0;j+b<=m;++b)
						tmp=1ll*now*C[m-j][b]%mod,
						add(f[u^1][i][j+b],(b&1)?mod-tmp:tmp),
						now=1ll*now*Pw%mod;
				}	
		u^=1;
		memset(f[u^1],0,sizeof(f[u^1]));
	}
	cout<<f[u][n][m];
	return 0;
}