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 int long long
const int N=105;
int n,m,K,M,dp[N][N][N][2],c[N][N],g1[N][N*N],g2[N][N][N];
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;	
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&K,&M);
	c[0][0]=1;
	for (int i=1;i<N;i++){
		c[i][0]=1;
		for (int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%M;
	}
	for (int i=0;i<N;i++)
		for (int j=0;j<N*N;j++)g1[i][j]=ksm(i,j);
	for (int i=0;i<N;i++)
		for (int j=0;j<N;j++)
			for (int k=0;k<N;k++)
				g2[i][j][k]=ksm((ksm(i,j)-(i==0?0:ksm(i-1,j))+M)%M,k);
	dp[0][0][0][0]=1;
	for (int k=0;k<K;k++){
		for (int j=0;j<=m;j++)
			for (int i=0;i<=n;i++)
				for (int p=0;p<=n-i;p++)
					(dp[i+p][j][k][1]+=dp[i][j][k][0]*c[n-i][p]%M*g1[K-k][j*p]%M*g2[k+1][m-j][p])%=M;
		for (int j=0;j<=m;j++)
			for (int i=0;i<=n;i++)
				for (int p=0;p<=m-j;p++)
					(dp[i][j+p][k+1][0]+=dp[i][j][k][1]*c[m-j][p]%M*g1[k+1][(n-i)*p]%M*g2[K-k][i][p])%=M;					
	}
	printf("%lld\n",dp[n][m][K][0]);
}