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;
typedef long long int ll;
const int maxn=105;
ll n,m,K,mod,f[maxn][maxn][maxn],C[maxn][maxn],pre[maxn][maxn*maxn];
ll tmp1[maxn][maxn],tmp2[maxn][maxn];
ll fac[maxn],inv[maxn];
inline ll qpow(ll x,ll y)
{
	ll ans=1,base=x;
	assert(y>=0);
	while(y)
	{
		if(y&1)
			ans=ans*base%mod;
		base=base*base%mod;
		y>>=1;
	}
	return ans;
}
inline void init()
{
	fac[0]=1;
	for(int i=1;i<=100;++i)
		fac[i]=fac[i-1]*i%mod;
	for(int i=0;i<=100;++i)
		inv[i]=qpow(fac[i],mod-2);
	C[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-1]+C[i-1][j])%mod;
	}
	for(int k=0;k<=K+2;++k)
	{
		pre[k][0]=1;
		for(int i=1;i<=n*m;++i)
			pre[k][i]=pre[k][i-1]*k%mod;
	}
}
inline void add(ll&x,ll y)
{
	x=(x+y)%mod;
}
inline void solve()
{
	f[0][0][0]=1;
	for(int k=0;k<K;++k)
	{
		memset(tmp1,0,sizeof(tmp1));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				for(int i1=0;i1+i<=n;++i1)
					add(tmp1[i+i1][j],f[i][j][k]*inv[i1]%mod*pre[K+1-(k+1)][i1*j]%mod*pre[k+1][(m-j)*i1]);
		memset(tmp2,0,sizeof(tmp2));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				for(int j1=0;j1+j<=m;++j1)
					add(tmp2[i][j+j1],tmp1[i][j]*inv[j1]%mod*pre[K+1-(k+1)][j1*i]%mod*pre[k+1][(n-i)*j1]);
		memset(tmp1,0,sizeof(tmp1));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				for(int i2=0;i2+i<=n;++i2)
					if(i2&1)
						add(tmp1[i+i2][j],-tmp2[i][j]*inv[i2]%mod*pre[K+1-(k+2)][i2*j]%mod*pre[k+1][(m-j)*i2]);
					else
						add(tmp1[i+i2][j],tmp2[i][j]*inv[i2]%mod*pre[K+1-(k+2)][i2*j]%mod*pre[k+1][(m-j)*i2]);
		memset(tmp2,0,sizeof(tmp2));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				for(int j2=0;j2+j<=m;++j2)
					if(j2&1)
						add(tmp2[i][j+j2],-tmp1[i][j]*inv[j2]%mod*pre[K+1-(k+2)][j2*i]%mod*pre[k+1][(n-i)*j2]);
					else
						add(tmp2[i][j+j2],tmp1[i][j]*inv[j2]%mod*pre[K+1-(k+2)][j2*i]%mod*pre[k+1][(n-i)*j2]);
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				f[i][j][k+1]=tmp2[i][j];
	}
	ll ans=f[n][m][K]*fac[n]%mod*fac[m]%mod;
	ans=(ans%mod+mod)%mod;
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>K>>mod;
	init();
	solve();
	return 0;
}