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<stdio.h>
int n,m,k,p;
int mt(int a,int b)
{
	if(b==0)
	{
		return 1;
	}
	int c=mt(a,b>>1);
	c=(long long)c*c%p;
	if(b&1)
	{
		c=(long long)c*a%p;
	}
	return c;
}
int dp[105][105],dp2[105][105],c[105][105];
int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&p);
	for(int i=0;i<=100;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			if(c[i][j]>=p)
			{
				c[i][j]-=p;
			}
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=k;i++)
	{
		for(int x=0;x<=n;x++)
		{
			for(int y=0;y<=m;y++)
			{
				dp2[x][y]=0;
			}
		}
		for(int x=0;x<=n;x++)
		{
			for(int y=0;y<=m;y++)
			{
				int val=mt(i,m-y)-mt(i-1,m-y);
				if(val<0)
				{
					val+=p;
				}
				val=(long long)val*mt(k-i+1,y)%p;
				int tmp=1;
				for(int d=0;d<=n-x;d++)
				{
					int inc=(long long)c[n-x][d]*tmp%p;
					dp2[x+d][y]+=(long long)dp[x][y]*inc%p;
					if(dp2[x+d][y]>=p)
					{
						dp2[x+d][y]-=p;
					}
					tmp=(long long)tmp*val%p;
				}
			}
		}
		for(int x=0;x<=n;x++)
		{
			for(int y=0;y<=m;y++)
			{
				dp[x][y]=0;
			}
		}
		for(int x=0;x<=n;x++)
		{
			for(int y=0;y<=m;y++)
			{
				int val=mt(k-i+1,x)-mt(k-i,x);
				if(val<0)
				{
					val+=p;
				}
				val=(long long)val*mt(i,n-x)%p;
				int tmp=1;
				for(int d=0;d<=m-y;d++)
				{
					int inc=(long long)c[m-y][d]*tmp%p;
					dp[x][y+d]+=(long long)dp2[x][y]*inc%p;
					if(dp[x][y+d]>=p)
					{
						dp[x][y+d]-=p;
					}
					tmp=(long long)tmp*val%p;
				}
			}
		}
	}
	printf("%d\n",dp[n][m]);
	return 0;
}