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 REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
#define mp(x,y) make_pair((x),(y))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int N=1e2+5;
int n,m,k,mod,f[N][N],g[N][N],coef[N][N],C[N][N],pw[N][N*N];
inline void inc(int& x,int y){x=x+y<mod?x+y:x+y-mod;}
inline void dec(int& x,int y){x=x-y>=0?x-y:x-y+mod;}

int main(){
    //freopen("in.in","r",stdin);
    n=read(),m=read(),k=read(),mod=read();
    REP(i,0,N-1)REP(j,C[i][0]=1,N-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    REP(i,0,N-1)REP(j,pw[i][0]=1,N*N-1)pw[i][j]=1ll*pw[i][j-1]*i%mod;
    f[0][0]=1;
    REP(h,1,k){
	memset(g,0,sizeof g);
	REP(j,0,m)REP(l,0,n)coef[j][l]=1ll*pw[k-h+1][l*j]*pw[h][l*(m-j)]%mod;
	REP(i,0,n)REP(j,0,m)if(f[i][j]){
	    REP(l,0,n-i){
		int c=1ll*f[i][j]*C[n-i][l]%mod*coef[j][l]%mod;
		inc(g[i+l][j],c);
	    }
	}
	memset(f,0,sizeof f);
	REP(i,0,n)REP(l,0,m)coef[i][l]=1ll*pw[k-h+1][l*i]*pw[h][l*(n-i)]%mod;
	REP(i,0,n)REP(j,0,m)if(g[i][j]){
	    REP(l,0,m-j){
		int c=1ll*g[i][j]*C[m-j][l]%mod*coef[i][l]%mod;
		inc(f[i][j+l],c);
	    }
	}
	memset(g,0,sizeof g);
	REP(j,0,m)REP(l,0,n)coef[j][l]=1ll*pw[k-h][l*j]*pw[h][l*(m-j)]%mod;
	REP(i,0,n)REP(j,0,m)if(f[i][j]){
	    REP(l,0,n-i){
		int c=1ll*f[i][j]*C[n-i][l]%mod*coef[j][l]%mod;
		l&1?dec(g[i+l][j],c):inc(g[i+l][j],c);
	    }
	}
	memset(f,0,sizeof f);
	REP(i,0,n)REP(l,0,m)coef[i][l]=1ll*pw[k-h][l*i]*pw[h][l*(n-i)]%mod;
	REP(i,0,n)REP(j,0,m)if(g[i][j]){
	    REP(l,0,m-j){
		int c=1ll*g[i][j]*C[m-j][l]%mod*coef[i][l]%mod;
		l&1?dec(f[i][j+l],c):inc(f[i][j+l],c);
	    }
	}
    }
    printf("%d\n",f[n][m]);
    return 0;
}
/*
  $f_{h,i,j}=\sum_{x=0}^i\sum_{y=0}^j\binom{n-(i-x)}{x}\binom{m-(j-y)}{y}f_{h-1,i-x,j-y}h^{x(m-(j-y))+y(n-(i-x))-xy}\sum_{p=0}^x\sum_{q=0}^y(-1)^{p+q} \binom{x}{p}\binom{y}{q} (k-h)^{p(j-y)+q(i-x)+pq}(k-h+1)^{(x-p)(j-y)+(y-q)(i-x)+(x-p)(y-q)}$
 */