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>
#define title "title"
#define ll long long
#define ull unsigned ll
#define fix(x) fixed<<setprecision(x)
#define pii pair<ll,ll>
#define vint vector<ll>
#define pb push_back
using namespace std;
void Freopen(){
	freopen(title".in","r",stdin);
	freopen(title".out","w",stdout);
}
ll read(){
	ll g=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){g=g*10+ch-'0';ch=getchar();}
	return g*f;
}
const ll N=1e2+5;
const ll maxn=1e2;
ll n,m,k,mod,C[N][N],P[N][N],f[2][N][N];
void clear(ll opt){
	for(ll i=0;i<=n;i++)for(ll j=0;j<=m;j++)f[opt][i][j]=0;
}
signed main(){
	n=read(),m=read(),k=read(),mod=read();
	for(ll i=0;i<=maxn;i++)C[i][0]=1;
	for(ll i=1;i<=maxn;i++)for(ll j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(ll i=0;i<=maxn;i++)P[i][0]=1;
	for(ll i=1;i<=maxn;i++)for(ll j=1;j<=maxn;j++)P[i][j]=P[i][j-1]*i%mod;
	ll now=1,last=0;f[0][0][0]=1;
	for(ll t=1;t<=k;t++){
		clear(now);for(ll i=0;i<=n;i++)for(ll j=0;j<=m;j++)if(f[last][i][j]){
			ll x=f[last][i][j],y=P[k-t+1][j]*P[t][m-j]%mod;
			for(ll a=0;i+a<=n;a++,x=x*y%mod)f[now][i+a][j]=(f[now][i+a][j]+C[n-i][a]*x%mod)%mod;
		}swap(now,last);
		clear(now);for(ll i=0;i<=n;i++)for(ll j=0;j<=m;j++)if(f[last][i][j]){
			ll x=f[last][i][j],y=P[k-t+1][i]*P[t][n-i]%mod;
			for(ll b=0;j+b<=m;b++,x=x*y%mod)f[now][i][j+b]=(f[now][i][j+b]+C[m-j][b]*x%mod)%mod;
		}swap(now,last);
		clear(now);for(ll i=0;i<=n;i++)for(ll j=0;j<=m;j++)if(f[last][i][j]){
			ll x=f[last][i][j],y=(mod-P[k-t][j])*P[t][m-j]%mod;
			for(ll a=0;i+a<=n;a++,x=x*y%mod)f[now][i+a][j]=(f[now][i+a][j]+C[n-i][a]*x%mod)%mod;
		}swap(now,last);
		clear(now);for(ll i=0;i<=n;i++)for(ll j=0;j<=m;j++)if(f[last][i][j]){
			ll x=f[last][i][j],y=(mod-P[k-t][i])*P[t][n-i]%mod;
			for(ll b=0;j+b<=m;b++,x=x*y%mod)f[now][i][j+b]=(f[now][i][j+b]+C[m-j][b]*x%mod)%mod;
		}swap(now,last);
	}return cout<<f[now][n][m],signed();
}
/*
2 2 2 998244353
2 3 4 998244353
31 41 59 998244353
*/