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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[110][110][110][2];
long long f1[110][110][110],f2[110][110][110];
long long g1[110][110][110],g2[110][110][110];
long long C[110][110];
long long Mod;
long long fpow(long long a,long long b)
{
	long long ans=1,t=a;
	while(b)
	{
		if(b&1)ans=ans*t%Mod;
		t=t*t%Mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	int n,m,k;
	scanf("%d %d %d %lld",&n,&m,&k,&Mod);
	for(int i=0;i<=max(n,m);i++)
		C[i][0]=C[i][i]=1;
	for(int i=2;i<=max(n,m);i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
	for(int p=1;p<=k;p++)
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				f1[p][i][j]=fpow((fpow(p,j)-fpow(p-1,j)+Mod)%Mod,i);
				f2[p][i][j]=fpow(fpow(p,i),j);
				g1[p][i][j]=fpow(fpow(k-p+1,i),j);
				g2[p][i][j]=fpow((fpow(k-p+1,i)-fpow(k-p,i)+Mod)%Mod,j);
			}
	dp[0][0][0][1]=1;
	for(int p=1;p<=k;p++)
	{
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				if(!dp[p-1][i][j][1])continue;
				for(int q=0;q<=n-i;q++)
					dp[p][i+q][j][0]=(dp[p][i+q][j][0]+
							dp[p-1][i][j][1]*C[n-i][q]%Mod
							*f1[p][q][m-j]%Mod*g1[p][q][j])%Mod;
			}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				if(!dp[p][i][j][0])continue;
				for(int q=0;q<=m-j;q++)
					dp[p][i][j+q][1]=(dp[p][i][j+q][1]+
							dp[p][i][j][0]*C[m-j][q]%Mod
							*f2[p][n-i][q]%Mod*g2[p][i][q])%Mod;
			}
	}
	printf("%lld\n",dp[k][n][m][1]);
	return 0;
}