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;

typedef long long LL;

const int N=100;

LL mod;
int n,m,sk;

void into(){
  scanf("%d%d%d%lld",&n,&m,&sk,&mod);
}

LL inv[N+9],fac[N+9],ifac[N+9];

void Get_inv(){
  inv[1]=1;
  fac[0]=fac[1]=1;
  ifac[0]=ifac[1]=1;
  for (int i=2,lim=max(n,m);i<=lim;++i){
	inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	fac[i]=fac[i-1]*i%mod;
	ifac[i]=ifac[i-1]*inv[i]%mod;
  }
}

LL pw[N+9][N*N+9];

void Get_pw(){
  for (int i=0;i<=sk;++i){
	pw[i][0]=1;
	for (int j=1;j<=n*m;++j) pw[i][j]=pw[i][j-1]*i%mod;
  }
}

LL dp[2][N+9][N+9];
int now,old;
LL tmp[N+9][N+9];

void Get_now(){
  now^=1;old^=1;
  for (int i=0;i<=n;++i)
	for (int j=0;j<=m;++j) dp[now][i][j]=0;
}

void Get_dp(){
  LL mod2=mod*mod;
  now=0;old=1;
  dp[now][0][0]=1;
  for (int i=1;i<=sk;++i){
	Get_now();
    for (int j=0;j<=n;++j)
	  for (int k=0;k<=m;++k) tmp[j][k]=ifac[j]*pw[i][j*(m-k)]%mod*pw[sk-i+1][j*k]%mod;
    for (int j=0;j<=n;++j)
      for (int k=0;k<=m;++k){
		for (int t=0;t<=j;++t){
		  dp[now][j][k]+=dp[old][j-t][k]*tmp[t][k];
		  if (dp[now][j][k]>=mod2) dp[now][j][k]-=mod2;
		}
		dp[now][j][k]%=mod;
	  }
	Get_now();
	for (int j=0;j<=m;++j)
	  for (int k=0;k<=n;++k) tmp[j][k]=ifac[j]*pw[i][j*(n-k)]%mod*pw[sk-i+1][j*k]%mod;
    for (int j=0;j<=n;++j)
	  for (int k=0;k<=m;++k){
		for (int t=0;t<=k;++t){
		  dp[now][j][k]+=dp[old][j][k-t]*tmp[t][j];
		  if (dp[now][j][k]>=mod2) dp[now][j][k]-=mod2;
		}
	    dp[now][j][k]%=mod;
	  }
	Get_now();
    for (int j=0;j<=n;++j)
	  for (int k=0;k<=m;++k){
		tmp[j][k]=ifac[j]*pw[i][j*(m-k)]%mod*pw[sk-i][j*k]%mod;
		if (j&1&&tmp[j][k]) tmp[j][k]=mod-tmp[j][k];
	  }
    for (int j=0;j<=n;++j)
      for (int k=0;k<=m;++k){
		for (int t=0;t<=j;++t){
		  dp[now][j][k]+=dp[old][j-t][k]*tmp[t][k];
		  if (dp[now][j][k]>=mod2) dp[now][j][k]-=mod2;
		}
		dp[now][j][k]%=mod;
	  }
	Get_now();
	for (int j=0;j<=m;++j)
	  for (int k=0;k<=n;++k){
		tmp[j][k]=ifac[j]*pw[i][j*(n-k)]%mod*pw[sk-i][j*k]%mod;
		if (j&1&&tmp[j][k]) tmp[j][k]=mod-tmp[j][k];
	  }
    for (int j=0;j<=n;++j)
	  for (int k=0;k<=m;++k){
		for (int t=0;t<=k;++t){
		  dp[now][j][k]+=dp[old][j][k-t]*tmp[t][j];
		  if (dp[now][j][k]>=mod2) dp[now][j][k]-=mod2;
		}
	    dp[now][j][k]%=mod;
	  }
  }
}

void work(){
  Get_inv();
  Get_pw();
  Get_dp();
}

void outo(){
  printf("%lld\n",dp[now][n][m]*fac[n]%mod*fac[m]%mod);
}

int main(){
  into();
  work();
  outo();
  return 0;
}