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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=117;
const int MM=100 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n,s;
LL dp[NN][NN][NN]={};
LL tp[NN][NN]={};
LL mod;
LL fact[NN]={};
LL rev[NN]={};
LL mi[NN][NN*NN]={};
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=ret*a%mod;
	return ret;
}
void prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i){
		fact[i]=fact[i-1]*i%mod;
	}
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i){
		rev[i-1]=rev[i]*i%mod;
	}
}
LL c[NN][NN]={};
int main(){
	//open();
	n=read();
	m=read();
	s=read();
	mod=read();
	prefact(max(n,m));
	for(int i=0;i<=s;++i){
		mi[i][0]=1;
		for(int j=1;j<=n*m;++j){
			mi[i][j]=mi[i][j-1]*i%mod;
		}
	}
	dp[1][n][m]=1;
	for(int i=1;i<=s;++i){
		for(int j=0;j<=n;++j){
			for(int l=0;l<=m;++l){
				c[j][l]=rev[l]*mi[i][j*l]%mod*mi[s-i+1][(n-j)*l]%mod;
			}
		}
		for(int j=0;j<=n;++j){
			for(int k=0;k<=m;++k){
				tp[j][k]=0;
				for(int l=0;l+k<=m;++l){
					tp[j][k]+=dp[i][j][k+l]*c[j][l];
					tp[j][k]%=mod;
				}
			}
		}
		for(int l=0;l<=n;++l){
			for(int k=0;k<=m;++k){
				c[l][k]=rev[l]*mi[i][k*l]%mod*mi[s-i+1][(m-k)*l]%mod;
			}
		}
		for(int j=0;j<=n;++j){
			for(int k=0;k<=m;++k){
				dp[i][j][k]=0;
				for(int l=0;l+j<=n;++l){
					dp[i][j][k]+=tp[j+l][k]*c[l][k];
					dp[i][j][k]%=mod;
				}
			}
		}
		for(int j=0;j<=n;++j){
			for(int l=0,sym=1;l<=m;++l,sym=-sym){
				c[j][l]=rev[l]*mi[i][j*l]*sym%mod*mi[s-i][(n-j)*l]%mod;
			}
		}
		for(int j=0;j<=n;++j){
			for(int k=0;k<=m;++k){
				tp[j][k]=0;
				for(int l=0;l+k<=m;++l){
					tp[j][k]+=dp[i][j][k+l]*c[j][l];
					tp[j][k]%=mod;
				}
			}
		}
		for(int l=0,sym=1;l<=n;++l,sym=-sym){
			for(int k=0;k<=m;++k){
				c[l][k]=rev[l]*mi[i][k*l]*sym%mod*mi[s-i][(m-k)*l]%mod;
			}
		}
		for(int j=0;j<=n;++j){
			for(int k=0;k<=m;++k){
				dp[i+1][j][k]=0;
				for(int l=0;l+j<=n;++l){
					dp[i+1][j][k]+=tp[j+l][k]*c[l][k];
					dp[i+1][j][k]%=mod;
				}
			}
		}
	}
	LL ans=dp[s+1][0][0]*fact[n]%mod*fact[m]%mod;
	ans=(ans+mod)%mod;
	printf("%lld\n",ans);
	close();
	return 0;
}