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
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=105;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,m,k,Mod,F[2][MAXN][MAXN],C[MAXN][MAXN],Fpow[MAXN][MAXN];
inline void pre(int n=100){
	Rep(i,0,n){C[i][0]=1;Rep(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;}
	Rep(i,1,n){Fpow[i][0]=1;Rep(j,1,n)Fpow[i][j]=1ll*Fpow[i][j-1]*i%Mod;}
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),m=read(),k=read(),Mod=read(),pre();
	F[0][0][0]=1;int now=0;
	Rep(t,1,k){
		memset(F[now^1],0,sizeof(F[now^1]));
		Rep(i,0,n)Rep(j,0,m)if(F[now][i][j]){
			for(int a=0,x=F[now][i][j],y=1ll*Fpow[k-t+1][j]*Fpow[t][m-j]%Mod;i+a<=n;a++,x=1ll*x*y%Mod)
				F[now^1][i+a][j]=(F[now^1][i+a][j]+1ll*C[n-i][a]*x)%Mod;
		}now^=1,memset(F[now^1],0,sizeof(F[now^1]));
		Rep(i,0,n)Rep(j,0,m)if(F[now][i][j]){
			for(int b=0,x=F[now][i][j],y=1ll*Fpow[k-t+1][i]*Fpow[t][n-i]%Mod;j+b<=m;b++,x=1ll*x*y%Mod)
				F[now^1][i][j+b]=(F[now^1][i][j+b]+1ll*C[m-j][b]*x)%Mod;
		}now^=1,memset(F[now^1],0,sizeof(F[now^1]));
		Rep(i,0,n)Rep(j,0,m)if(F[now][i][j]){
			for(int c=0,x=F[now][i][j],y=1ll*(Mod-Fpow[k-t][j])*Fpow[t][m-j]%Mod;i+c<=n;c++,x=1ll*x*y%Mod)
				F[now^1][i+c][j]=(F[now^1][i+c][j]+1ll*C[n-i][c]*x)%Mod;
		}now^=1,memset(F[now^1],0,sizeof(F[now^1]));
		Rep(i,0,n)Rep(j,0,m)if(F[now][i][j]){
			for(int d=0,x=F[now][i][j],y=1ll*(Mod-Fpow[k-t][i])*Fpow[t][n-i]%Mod;j+d<=m;d++,x=1ll*x*y%Mod)
				F[now^1][i][j+d]=(F[now^1][i][j+d]+1ll*C[m-j][d]*x)%Mod;
		}now^=1;
	}cout<<F[now][n][m]<<"\n";
	return 0;
}