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>
#define ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
ll cef[110][110][110][2],f[110][110][110][2],n,m,K,mod,C[110][110];
ll fp(ll a,ll k){
	ll ans=1;
	for(;k;k>>=1,a=a*a%mod)
		if(k&1) ans=a*ans%mod;
	return ans;
}
void upd(ll&a,ll b){a=(a+b)%mod;}
int main(){
	read(n);read(m);read(K);read(mod);
	for(int i=0;i<=100;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;
	}
	for(int p=0;p<=n;p++)
		for(int k=1;k<=K;k++)
			for(int i=0;i<=m;i++)
				cef[p][k][i][0]=fp((fp(k,m-i)-fp(k-1,m-i))*fp(K-k+1,i)%mod,p);
	for(int p=0;p<=m;p++)
		for(int k=1;k<=K;k++)
			for(int i=0;i<=n;i++)
				cef[p][k][i][1]=fp(fp(k,n-i)*(fp(K-k+1,i)-fp(K-k,i))%mod,p);
	f[0][0][0][0]=1;
	for(int k=0;k<K;k++)
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++){
				for(int p=0;p+i<=n;p++)
					upd(f[k][i+p][j][1],f[k][i][j][0]*cef[p][k+1][j][0]%mod*C[n-i][p]);
				for(int p=0;p+j<=m;p++)
					upd(f[k+1][i][j+p][0],f[k][i][j][1]*cef[p][k+1][i][1]%mod*C[m-j][p]);
			}
	cout<<(f[K][n][m][0]+mod)%mod<<'\n';
	return 0;
}