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<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
using namespace std;
#define G getchar()
int read()
{
	int x=0; char ch=G;
	for (;!isdigit(ch);ch=G);
	for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);
	return x;
}
#undef G
typedef long long ll;
const int MAXW=100;
int Mod;
int qpow(int x,int y){
	int res=1;
	for (;y;y>>=1,x=1LL*x*x%Mod)
		if (y&1) res=1LL*res*x%Mod;
	return res;
}
int fac[110],ifac[110];

int n,m,K,nm;
int dp[2][110][110]; bool dpcur;
inline void add(int &x,ll y){x=(x+y)%Mod;}
int p[110][10010];
int trans[110][110];
int main()
{
	n=read(),m=read(),K=read(),Mod=read(); nm=n*m;
	fac[0]=1; for (int i=1;i<=MAXW;i++) fac[i]=1LL*fac[i-1]*i%Mod;
	ifac[MAXW]=qpow(fac[MAXW],Mod-2); for (int i=MAXW;i;i--) ifac[i-1]=1LL*ifac[i]*i%Mod;
	for (int i=0;i<=K;i++){
		p[i][0]=1;
		for (int j=1;j<=nm;j++) p[i][j]=1LL*p[i][j-1]*i%Mod;
	}
	dp[dpcur][0][0]=1;
	for (int k=1;k<=K;k++){
		dpcur^=1; memset(dp[dpcur],0,sizeof dp[dpcur]);
		for (int u=0;u<=n;u++)
			for (int j=0;j<=m;j++)
				trans[u][j]=1LL*ifac[u]*p[k][u*(m-j)]%Mod*p[K-k+1][u*j]%Mod;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++)
				for (int u=0;i+u<=n;u++){
					add(dp[dpcur][i+u][j],1LL*dp[dpcur^1][i][j]*trans[u][j]);
				}
		dpcur^=1; memset(dp[dpcur],0,sizeof dp[dpcur]);
		for (int i=0;i<=n;i++)
			for (int v=0;v<=m;v++)
				trans[i][v]=1LL*ifac[v]*p[k][v*(n-i)]%Mod*p[K-k+1][v*i]%Mod;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++)
				for (int v=0;j+v<=m;v++){
					add(dp[dpcur][i][j+v],1LL*dp[dpcur^1][i][j]*trans[i][v]);
				}
		dpcur^=1; memset(dp[dpcur],0,sizeof dp[dpcur]);
		for (int u=0;u<=n;u++)
			for (int j=0;j<=m;j++)
				trans[u][j]=1LL*ifac[u]*p[k][u*(m-j)]%Mod*p[K-k][u*j]%Mod;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++){
				for (int u=0;i+u<=n;u+=2){
					add(dp[dpcur][i+u][j],1LL*dp[dpcur^1][i][j]*trans[u][j]);
				}
				for (int u=1;i+u<=n;u+=2){
					add(dp[dpcur][i+u][j],-1LL*dp[dpcur^1][i][j]*trans[u][j]);
				}
			}
		dpcur^=1; memset(dp[dpcur],0,sizeof dp[dpcur]);
		for (int i=0;i<=n;i++)
			for (int v=0;v<=m;v++)
				trans[i][v]=1LL*ifac[v]*p[k][v*(n-i)]%Mod*p[K-k][v*i]%Mod;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++){
				for (int v=0;j+v<=m;v+=2){
					add(dp[dpcur][i][j+v],1LL*dp[dpcur^1][i][j]*trans[i][v]);
				}
				for (int v=1;j+v<=m;v+=2){
					add(dp[dpcur][i][j+v],-1LL*dp[dpcur^1][i][j]*trans[i][v]);
				}
			}
	}
	int ans=1LL*dp[dpcur][n][m]*fac[n]%Mod*fac[m]%Mod;
	printf("%d\n",(ans+Mod)%Mod);
	return 0;
}