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 re register
#define ull unsigned int
using namespace std;
inline int read(){
	int s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
const int N=105;
int n,m,K,P,o;
int coe[N],C[N][N],p[N][N],f[2][N][N],tp[N][N];
int Mod(int x){return x>=P?x-P:x;}
void Pre(int n){
	coe[0]=1;for(int i=1;i<=n;i++)coe[i]=P-coe[i-1];
	for(int i=0;i<=n;i++){
		C[i][0]=p[i][0]=1;
		for(int j=1;j<=n;j++)p[i][j]=1ll*p[i][j-1]*i%P;
		for(int j=1;j<=i;j++)C[i][j]=Mod(C[i-1][j-1]+C[i-1][j]);
	}
}
void Clear(int t){
	for(int i=0;i<=n;i++)
	for(int j=0;j<=m;j++)f[t][i][j]=0;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),K=read(),P=read(),Pre(100);
	f[0][0][0]=1;
	for(int t=1;t<=K;t++){
		o^=1,Clear(o);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*p[K-t+1][j]*p[t][m-j]%P,y=f[o^1][i][j];
			for(int a=0;a<=n-i;a++,y=1ll*y*x%P)f[o][i+a][j]=Mod(f[o][i+a][j]+1ll*C[n-i][a]%P*y%P);
		}o^=1,Clear(o);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*p[K-t+1][i]*p[t][n-i]%P,y=f[o^1][i][j];
			for(int b=0;b<=m-j;b++,y=1ll*y*x%P)f[o][i][j+b]=Mod(f[o][i][j+b]+1ll*C[m-j][b]%P*y%P);
		}o^=1,Clear(o);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*(P-p[K-t][j])*p[t][m-j]%P,y=f[o^1][i][j];
			for(int a=0;a<=n-i;a++,y=1ll*y*x%P)f[o][i+a][j]=Mod(f[o][i+a][j]+1ll*C[n-i][a]%P*y%P);
		}o^=1,Clear(o);	
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*(P-p[K-t][i])*p[t][n-i]%P,y=f[o^1][i][j];
			for(int b=0;b<=m-j;b++,y=1ll*y*x%P)f[o][i][j+b]=Mod(f[o][i][j+b]+1ll*C[m-j][b]%P*y%P);
		}
	}printf("%d",f[o][n][m]);
	return 0;
}
/*2 2 2 998244353*/