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,C[110][110],K,mod,p[110][110],f[2][110][110];
void clean(int o){for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)f[o][i][j]=0;}
int main()
{
	scanf("%d%d%d%d",&n,&m,&K,&mod);
	for(int i=0;i<=max(n,m);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=1;i<=K;i++)
	{
		p[i][0]=1;
		for(int j=1;j<=max(n,m);j++)p[i][j]=1ll*p[i][j-1]*i%mod;
	}
	f[0][0][0]=1;int o=0;
	for(int k=1;k<=K;k++)
	{
		clean(o^1);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)
		{
			int x=f[o][i][j],y=1ll*p[K-k+1][j]*p[k][m-j]%mod;
			for(int a=0;i+a<=n;a++,x=1ll*x*y%mod)f[o^1][i+a][j]=(f[o^1][i+a][j]+1ll*C[n-i][a]*x)%mod;
		}
		o^=1; 
		clean(o^1);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)
		{
			int x=f[o][i][j],y=1ll*p[K-k+1][i]*p[k][n-i]%mod;
			for(int b=0;j+b<=m;b++,x=1ll*x*y%mod)f[o^1][i][j+b]=(f[o^1][i][j+b]+1ll*C[m-j][b]*x)%mod;
		}
		o^=1; 
		clean(o^1);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)
		{
			int x=f[o][i][j],y=1ll*-p[K-k][j]*p[k][m-j]%mod;
			for(int a=0;i+a<=n;a++,x=1ll*x*y%mod)f[o^1][i+a][j]=(f[o^1][i+a][j]+1ll*C[n-i][a]*x)%mod;
		}
		o^=1; 
		clean(o^1);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)
		{
			int x=f[o][i][j],y=1ll*-p[K-k][i]*p[k][n-i]%mod;
			for(int b=0;j+b<=m;b++,x=1ll*x*y%mod)f[o^1][i][j+b]=(f[o^1][i][j+b]+1ll*C[m-j][b]*x)%mod;
		}
		o^=1; 
	} 
	printf("%d",(f[o][n][m]+mod)%mod);
	return 0;
}