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;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=120;

int n,m,k,mod;
int jc[maxn],jcn[maxn],inv[maxn];
int pw[maxn][maxn*maxn];
int pwinv[maxn][maxn*maxn];

inline void init()
{
	n=read();m=read();k=read();mod=read();
	jc[0]=jc[1]=jcn[0]=jcn[1]=inv[1]=1;
	REP(i,2,100)jc[i]=(ll)jc[i-1]*i%mod,inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod,jcn[i]=(ll)jcn[i-1]*inv[i]%mod;
	REP(i,0,k)
	{
		pw[i][0]=pwinv[i][0]=1;
		REP(j,1,n*m)pw[i][j]=(ll)pw[i][j-1]*i%mod,pwinv[i][j]=(ll)pwinv[i][j-1]*inv[i]%mod;
	}
}

int f[maxn][maxn][maxn];
int g[maxn][maxn];

inline void doing()
{
	f[k+1][0][0]=1;
	REP(i,0,n)REP(j,0,m)f[k][i][j]=(ll)pw[k][i*j]*jcn[i]%mod*jcn[j]%mod;
	
	DREP(val,k-1,1)
	{
		/*REP(i,0,n)REP(j,0,m)REP(x,i,n)REP(y,j,m)REP(a,x,n)REP(b,y,m)
		{
			f[val][a][b]=(f[val][a][b]+(ll)f[val+1][i][j]*pw[val][a*b-i*j]%mod*jcn[x-i]%mod*jcn[y-j]%mod*jcn[a-x]%mod*jcn[b-y]%mod*pw[k-val][(n-i)*(m-j)-(n-x)*(m-y)]%mod*pw[k-val+1][(n-x)*(m-y)-(n-a)*(m-b)]%mod*(x+y-i-j&1?-1:1))%mod;
			}*/
		memset(g,0,sizeof(g));
		REP(i,0,n)REP(j,0,m)g[i][j]=(ll)f[val+1][i][j]*pwinv[val][i*j]%mod*pw[k-val][(n-i)*(m-j)]*(i+j&1?-1:1)%mod;
		DREP(i,n,0)DREP(j,m,0)
			REP(x,i+1,n)g[x][j]=(g[x][j]+(ll)g[i][j]*jcn[x-i])%mod;
		DREP(i,n,0)DREP(j,m,0)
			REP(y,j+1,m)g[i][y]=(g[i][y]+(ll)g[i][j]*jcn[y-j])%mod;
		REP(x,0,n)REP(y,0,m)g[x][y]=(ll)g[x][y]*pwinv[k-val][(n-x)*(m-y)]%mod*pw[k-val+1][(n-x)*(m-y)]*(x+y&1?-1:1)%mod;
		DREP(i,n,0)DREP(j,m,0)
			REP(x,i+1,n)g[x][j]=(g[x][j]+(ll)g[i][j]*jcn[x-i])%mod;
		DREP(i,n,0)DREP(j,m,0)
			REP(y,j+1,m)g[i][y]=(g[i][y]+(ll)g[i][j]*jcn[y-j])%mod;
		REP(a,0,n)REP(b,0,m)g[a][b]=(ll)g[a][b]*pw[val][a*b]%mod*pwinv[k-val+1][(n-a)*(m-b)]%mod;
		REP(i,0,n)REP(j,0,m)f[val][i][j]=g[i][j];
	}
	int ans=(ll)f[1][n][m]*jc[n]%mod*jc[m]%mod;
	ans=(ans+mod)%mod;
	printf("%d\n",ans);
}

int main()
{
	init();
	doing();
	return 0;
}