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 LL long long
#define db double

using namespace std;
const int N=100+10,M=N*N;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int mod;
void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}
int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}return an;}
int ginv(int a){return fpow(a,mod-2);}
vector<int> e[N];
int n,m,k,c[N][N],pw[N][M],f[2][N][N],g[N][N];

int main()
{
    n=rd(),m=rd(),k=rd(),mod=rd();
    for(int i=0;i<=N-5;++i)
    {
	c[i][0]=1;
	for(int j=1;j<=i;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    for(int i=0;i<=N-5;++i)
    {
	pw[i][0]=1;
	for(int j=1;j<=M-5;++j) pw[i][j]=1ll*pw[i][j-1]*i%mod;
    }
    int nw=1,la=0,dx;
    f[la][0][0]=1;
    for(int h=1;h<=k;++h)
	for(int o=0;o<=1;++o)
	{
	    for(int j=0;j<=m;++j)
		for(int l=0;l<=n;++l)
		    g[j][l]=1ll*pw[k-h+1-o][l*j]*pw[h][l*(m-j)]%mod;
	    for(int i=0;i<=n;++i)
		for(int j=0;j<=m;++j)
		{
		    if(!f[la][i][j]) continue;
		    for(int l=0;i+l<=n;++l)
		    {
			dx=1ll*f[la][i][j]*c[n-i][l]%mod*g[j][l]%mod;
			ad(f[nw][i+l][j],(o&l&1)?mod-dx:dx);
		    }
		    f[la][i][j]=0;
		}
	    nw^=1,la^=1;
	    for(int i=0;i<=n;++i)
		for(int l=0;l<=m;++l)
		    g[i][l]=1ll*pw[k-h+1-o][l*i]*pw[h][l*(n-i)]%mod;
	    for(int i=0;i<=n;++i)
		for(int j=0;j<=m;++j)
		{
		    if(!f[la][i][j]) continue;
		    for(int l=0;j+l<=m;++l)
		    {
			dx=1ll*f[la][i][j]*c[m-j][l]%mod*g[i][l]%mod;
			ad(f[nw][i][j+l],(o&l&1)?mod-dx:dx);
		    }
		    f[la][i][j]=0;
		}
	    nw^=1,la^=1;
	}
    printf("%d\n",f[la][n][m]);
    return 0;
}