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<iostream>
#include<cstdio>
#define cf(x) ((x)&1?P-1:1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=110,M=10010;
int n,m,K,P,T,nv,p[M],q[M],r[M],v[M],f[N][N],c[N][N],g[N][N];
void chk(int&x){x-=P;x+=(x>>31)&P;}
int qpw(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%P)if(y&1) z=1ll*z*x%P;return z;}
void work(int x){
	p[0]=q[0]=r[0]=v[0]=1;nv=qpw(K-x+1,P-2);
	FOR(i,1,T) p[i]=1ll*p[i-1]*x%P,q[i]=1ll*q[i-1]*(x-1)%P;
	FOR(i,1,T) r[i]=1ll*r[i-1]*(K-x+1)%P,v[i]=1ll*v[i-1]*nv%P;
	FOR(i,0,n)FOR(j,0,n) g[i][j]=1ll*q[i*j]*cf(j)%P;
	FOR(i,0,n)FOR(j,0,m) f[i][j]=1ll*f[i][j]*r[(n-i)*(m-j)]%P;
	ROF(i,n,0)ROF(j,m,0)FOR(k,0,i-1) chk(f[i][j]+=1ll*f[k][j]*c[n-k][i-k]%P*p[j*(i-k)]%P);
	ROF(i,n,0)ROF(j,m,0)FOR(k,0,j-1) chk(f[i][j]+=1ll*f[i][k]*c[m-k][j-k]%P*p[i*(j-k)]%P);
	//FOR(i,0,n)FOR(j,0,m) cout<<f[i][j]<<" \n"[j==m];
	ROF(i,n,0)ROF(j,m,0)FOR(k,0,i-1) chk(f[i][j]+=1ll*f[k][j]*c[n-k][i-k]%P*g[j][i-k]%P);
	ROF(i,n,0)ROF(j,m,0)FOR(k,0,j-1) chk(f[i][j]+=1ll*f[i][k]*c[m-k][j-k]%P*g[i][j-k]%P);
	FOR(i,0,n)FOR(j,0,m) f[i][j]=1ll*f[i][j]*v[(n-i)*(m-j)]%P;
	//FOR(i,0,n)FOR(j,0,m) cout<<f[i][j]<<" \n"[j==m];
}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&K,&P);
	if(n<m) swap(n,m);T=n*m;
	FOR(i,0,n) c[i][0]=1;
	FOR(i,1,n)FOR(j,1,i) c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
	f[0][0]=1;
	FOR(i,1,K) work(K-i+1);
	cout<<f[n][m]<<'\n';
}