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 ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;

int n,m,k,mod,c[111][111];
inline void add(int&x,int y){x+=y;if(x>=mod)x-=mod;}

int f[111][111][111],g[111][111][111];
int qpow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=(LL)ret*x%mod;
		x=(LL)x*x%mod;
		y>>=1;
	}
	return ret;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&mod);
	for(int i=0;i<111;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			if(c[i][j]>=mod)c[i][j]-=mod;
		}
	}
	
	f[1][0][0]=1;
	for(int v=1;v<=k;v++)
	{
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[v][i][j])
		{
			int row=qpow(v,m-j)-qpow(v-1,m-j);if(row<0)row+=mod;
			int col=qpow(k-v+1,j),p=1;
			for(int ni=0;ni<=n-i;ni++)
			{
				add(g[v][i+ni][j],(LL)f[v][i][j]*c[n-i][ni]%mod*p%mod);
				p=(LL)p*row%mod*col%mod;
			}
		}
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(g[v][i][j])
		{
			int row=qpow(v,n-i),p=1;
			int col=qpow(k-v+1,i)-qpow(k-v,i);if(col<0)col+=mod;
			for(int nj=0;nj<=m-j;nj++)
			{
				add(f[v+1][i][j+nj],(LL)g[v][i][j]*c[m-j][nj]%mod*p%mod);
				p=(LL)p*row%mod*col%mod;
			}
		}
	}
	printf("%d\n",f[k+1][n][m]);
	return 0;
}