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 ll;
const int N=105,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,m,K,p,C[N][N],f[N][N][N][2],g[N][N][N][2];
char ch[N];
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
void check(int &x,int y){x=(x+y<p) ? (x+y) : (x+y-p);}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=read();m=read();K=read();p=read();
	for (int i=0;i<=max(n,m);i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++)
		C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
	}
	f[0][0][0][0]=1;
	for (int k=0;k<=K;k++){
		for (int j=0;j<=m;j++)
		g[k][0][j][0]=1,g[k][1][j][0]=(ll)qpow(K-k,j)*(qpow(k+1,m-j)-qpow(k,m-j)+p)%p;
		for (int i=0;i<=n;i++)
		g[k][i][0][1]=1,g[k][i][1][1]=(ll)(qpow(K-k,i)-qpow(K-k-1,i)+p)*qpow(k+1,n-i)%p;
		for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++){
			if (i>1) g[k][i][j][0]=(ll)g[k][i-1][j][0]*g[k][1][j][0]%p;
			if (j>1) g[k][i][j][1]=(ll)g[k][i][j-1][1]*g[k][i][1][1]%p;
		}
	}
	for (int d=0;d<K;d++){
		for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
		for (int k=0;i+k<=n;k++)
		check(f[d][i+k][j][1],(ll)f[d][i][j][0]*g[d][k][j][0]%p*C[n-i][k]%p);
		for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
		for (int k=0;j+k<=m;k++)
		check(f[d+1][i][j+k][0],(ll)f[d][i][j][1]*g[d][i][k][1]%p*C[m-j][k]%p);
	}
	printf("%d\n",f[K][n][m][0]);
	return 0;
}