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 ll long long

ll f[110][110],h[110][110];
ll bin[110][10010],fac[110],ifac[110];
ll n,m,K,mod;

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll pls(const ll &x,const ll &y) { return (x+y<mod)?x+y:x+y-mod; }
inline ll mns(const ll &x,const ll &y) { return (x-y<0)?x-y+mod:x-y; }
inline ll ksm(ll x,ll y) { ll res=1;for (;y;y>>=1,x=x*x%mod) if (y&1) res=res*x%mod;return res; }

inline void pre_gao()
{
	fac[0]=1;
	for (int i=1;i<=100;i++) fac[i]=fac[i-1]*i%mod;
	ifac[100]=ksm(fac[100],mod-2);
	for (int i=99;~i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	for (int i=1;i<=K;i++)
	{
		bin[i][0]=1;
		for (int j=1;j<=10000;j++) bin[i][j]=bin[i][j-1]*i%mod;
	}
}

int main()
{
	n=rd();m=rd();K=rd();mod=rd();pre_gao();
	f[0][0]=1;
	for (int k=1;k<=K;k++)
	{
		for (int l=1;l<=n;l++) for (int j=0;j<=m;j++) h[l][j]=ifac[l]*bin[K-k+1][l*j]%mod*bin[k][l*(m-j)]%mod;
		for (int i=n;i;i--) for (int j=0;j<=m;j++) for (int l=1;l<=i;l++) f[i][j]=(f[i][j]+f[i-l][j]*h[l][j])%mod;
		for (int l=1;l<=m;l++) for (int i=0;i<=n;i++) h[l][i]=ifac[l]*bin[K-k+1][l*i]%mod*bin[k][l*(n-i)]%mod;
		for (int i=0;i<=n;i++) for (int j=m;j;j--) for (int l=1;l<=j;l++) f[i][j]=(f[i][j]+f[i][j-l]*h[l][i])%mod;
		for (int l=1;l<=n;l++) for (int j=0;j<=m;j++) h[l][j]=ifac[l]*bin[K-k][l*j]%mod*bin[k][l*(m-j)]%mod*((l&1)?(mod-1):1)%mod;
		for (int i=n;i;i--) for (int j=0;j<=m;j++) for (int l=1;l<=i;l++) f[i][j]=(f[i][j]+f[i-l][j]*h[l][j])%mod;
		for (int l=1;l<=m;l++) for (int i=0;i<=n;i++) h[l][i]=ifac[l]*bin[K-k][l*i]%mod*bin[k][l*(n-i)]%mod*((l&1)?(mod-1):1)%mod;
		for (int i=0;i<=n;i++) for (int j=m;j;j--) for (int l=1;l<=j;l++) f[i][j]=(f[i][j]+f[i][j-l]*h[l][i])%mod;
	}
	printf("%lld\n",f[n][m]*fac[n]%mod*fac[m]%mod);
	return 0;
}