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;

const int maxn=105;
int n,m,k,mod;
int fac[maxn],ifac[maxn],pw[maxn][maxn];
int f[maxn][maxn][maxn],g[maxn][maxn][maxn];
void Add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&k,&mod);
	fac[0]=ifac[0]=fac[1]=ifac[1]=1;
	for(int i=2;i<=max(n,m);i++){
		fac[i]=1LL*fac[i-1]*i%mod;
		ifac[i]=1LL*ifac[mod%i]*(mod-mod/i)%mod;
	}
	for(int i=1;i<=max(n,m);i++)ifac[i]=1LL*ifac[i-1]*ifac[i]%mod;
	pw[0][0]=1;
	for(int p=1;p<=k;p++){
		pw[p][0]=1;
		for(int i=1;i<=max(n,m);i++)pw[p][i]=1LL*pw[p][i-1]*p%mod;
	}
	f[0][0][0]=1;
	for(int p=0;p<=k;p++)for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
		if(g[p][i][j]){
			Add(f[p][i][j],g[p][i][j]);
			int coef=g[p][i][j],mul=pw[k-p+1][i]-pw[k-p][i];
			if(mul<0)mul+=mod;
			mul=1LL*mul*pw[p][n-i]%mod;
			for(int jj=j+1;jj<=m;jj++){
				coef=1LL*coef*mul%mod;
				Add(f[p][i][jj],1LL*ifac[jj-j]*coef%mod);
			}
		}
		if(p<k&&f[p][i][j]){
			Add(g[p+1][i][j],f[p][i][j]);
			int coef=f[p][i][j],mul=pw[p+1][m-j]-pw[p][m-j];
			if(mul<0)mul+=mod;
			mul=1LL*mul*pw[k-p][j]%mod;
			for(int ii=i+1;ii<=n;ii++){
				coef=1LL*coef*mul%mod;
				Add(g[p+1][ii][j],1LL*ifac[ii-i]*coef%mod);
			}
		}
	}
	printf("%d\n",1LL*f[k][n][m]*fac[n]%mod*fac[m]%mod);
	return 0;
}