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;

int n,m,k,mod,f[110][110][110],g[110][110][110],mi[110][10010],h[110][110][110],jc[110],inv[110];

int quickmi(int a,int b)
{
	int t=1;
	for (; b; b>>=1,a=1ll*a*a%mod)
		if (b&1) t=1ll*t*a%mod;
	return t;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&mod),jc[0]=1;
	for (int i=1; i<=100; i++) jc[i]=1ll*jc[i-1]*i%mod;
	inv[100]=quickmi(jc[100],mod-2);
	for (int i=100; i; i--) inv[i-1]=1ll*inv[i]*i%mod;
	for (int i=0; i<=k; i++)
	{
		mi[i][0]=1;
		for (int j=1; j<=n*m; j++) mi[i][j]=1ll*mi[i][j-1]*i%mod;
	}
	for (int i=1; i<=k; i++)
	{
		h[i][1][0]=0,h[i][0][0]=1;
		for (int j=1; j<=100; j++) h[i][0][j]=1,h[i][1][j]=(mi[i][j]-mi[i-1][j]+mod)%mod;
		for (int j=2; j<=100; j++)
		{
			h[i][j][0]=0;
			for (int k=1; k<=100; k++) h[i][j][k]=1ll*h[i][j-1][k]*h[i][1][k]%mod;
		}
	}
	g[0][0][0]=1ll*jc[n]*jc[m]%mod;
	for (int i=1; i<=k; i++)
	{
		for (int j=0; j<=n; j++)
			for (int l=0; l<=m; l++) if (g[i-1][j][l])
				for (int o=j; o<=n; o++) 
					f[i][o][l]=(f[i][o][l]+1ll*g[i-1][j][l]*mi[k-i+1][l*(o-j)]%mod*h[i][o-j][m-l]%mod*inv[o-j])%mod;
		for (int j=0; j<=n; j++)
			for (int l=0; l<=m; l++) if (f[i][j][l])
				for (int o=l; o<=m; o++) 
					g[i][j][o]=(g[i][j][o]+1ll*f[i][j][l]*mi[i][(o-l)*(n-j)]%mod*h[k-i+1][o-l][j]%mod*inv[o-l])%mod;
	}
	return printf("%d\n",g[k][n][m]),0;
}