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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,K,P;
#define Maxn 105
int calc[Maxn][Maxn][Maxn][2],C[Maxn][Maxn],dp[Maxn][Maxn][Maxn][2];

inline int Fast_Pow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=1ll*res*a%P;
		a=1ll*a*a%P;
		b>>=1; 
	}
	return res;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&K,&P);
	dp[1][0][0][0]=1;
	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]+C[i-1][j-1])%P;
	}
	for(int i=1;i<=K;++i)
	   for(int j=0;j<=m;++j)
	       for(int k=0;k<=n;++k){
	       	    int tmp=(Fast_Pow(i,m-j)-Fast_Pow(i-1,m-j)+P)%P;
	       	    tmp=1ll*tmp*Fast_Pow(K-i+1,j)%P;
	       	    calc[i][j][k][0]=Fast_Pow(tmp,k);
		   } 
	for(int i=1;i<=K;++i)
	    for(int j=0;j<=n;++j)
	        for(int k=0;k<=m;++k){
	        	int tmp=(Fast_Pow(K-i+1,j)-Fast_Pow(K-i,j)+P)%P;
	        	tmp=1ll*tmp*Fast_Pow(i,n-j)%P;
				calc[i][j][k][1]=Fast_Pow(tmp,k); 
			}
	for(int t=1;t<=K;++t)
	   for(int i=0;i<=n;++i)
            for(int j=0;j<=m;++j){
            	int tmp=dp[t][i][j][0];
				for(int k=0;i+k<=n;++k)
				    dp[t][i+k][j][1]=(dp[t][i+k][j][1]+1ll*tmp*C[n-i][k]%P*calc[t][j][k][0])%P;
				tmp=dp[t][i][j][1];
				for(int k=0;k<=m-j;++k)
				    dp[t+1][i][j+k][0]=(dp[t+1][i][j+k][0]+1ll*tmp*C[m-j][k]%P*calc[t][i][k][1])%P; 
			}
	printf("%d\n",dp[K+1][n][m][0]);
	return 0;
}