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 ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
#define mp make_pair
#define fi first
#define se second
int read(){
	char c=getchar();int d=0,f=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());
	return d*f;
}
using namespace std;
typedef long long LL;
const int N=105;
int n,m,k,Mo,C[N+1][N+1],f[N+1][N+1][N+1][2];
int mi(int a,int b){
	int s=1;
	for(;b;b>>=1,a=(LL)a*a%Mo)
		if(b&1)s=(LL)s*a%Mo;
	return s;
}
int main() {
	scanf("%d%d%d%d",&n,&m,&k,&Mo);
	ref(i,0,N)C[i][0]=1;
	ref(i,1,N)ref(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mo;
	f[0][0][0][0]=1;
	ref(x,0,k-1)ref(i,0,n)ref(j,0,m){
		int s=1,ss=(Mo+mi(x+1,m-j)-mi(x,m-j))%Mo;
		ss=(LL)ss*mi(k-x,j)%Mo;
		ref(l,0,n-i){
			(f[x][i+l][j][1]+=(LL)f[x][i][j][0]*C[n-i][l]%Mo*s%Mo)%=Mo;
			s=(LL)s*ss%Mo;
		}
		s=1;ss=(Mo+mi(k-x,i)-mi(k-x-1,i))%Mo;
		ss=(LL)ss*mi(x+1,n-i)%Mo;
		ref(l,0,m-j){
			(f[x+1][i][j+l][0]+=(LL)f[x][i][j][1]*C[m-j][l]%Mo*s%Mo)%=Mo;
			s=(LL)s*ss%Mo;
		}
	}
	printf("%d\n",f[k][n][m][0]);
	return 0;
}