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;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=105;
ll f[N][N][N],g[N][N][N],mod2;
int c[N][N],ycf[N][N][N],ycg[N][N][N],mod;
ll ksm(ll a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
int main(){
	int n=read(),m=read(),K=read(); mod=read(); mod2=(ll)mod*mod*7;
	For(i,1,K)For(k,0,m){
		ll xs=(ksm(i,m-k)-ksm(i-1,m-k)+mod)*ksm(K-i+1,k)%mod; 
		For(l,ycf[i][k][0]=1,n)ycf[i][k][l]=ycf[i][k][l-1]*xs%mod;
	}
	For(i,1,K)For(j,0,n){
		ll xs=(ksm(K-i+1,j)-ksm(K-i,j)+mod)*ksm(i,n-j)%mod;
		For(l,ycg[i][j][0]=1,m)ycg[i][j][l]=ycg[i][j][l-1]*xs%mod;
	}
	For(i,0,max(n,m))For(j,c[i][0]=1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	f[1][0][0]=1;
	For(i,1,K){
		For(j,0,n)For(k,0,m){
			f[i][j][k]%=mod; g[i][j][k]%=mod;
			For(l,0,n-j){
				g[i][j+l][k]+=f[i][j][k]*c[n-j][l]%mod*ycf[i][k][l];
				if(g[i][j+l][k]>=mod2)g[i][j+l][k]-=mod2;
			}
			For(l,0,m-k){
				f[i+1][j][k+l]+=g[i][j][k]*c[m-k][l]%mod*ycg[i][j][l];
				if(f[i+1][j][k+l]>=mod2)f[i+1][j][k+l]-=mod2;
			}
		}
	}
	cout<<f[K+1][n][m]%mod<<endl;
}