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;
//const int M=1000000007;
const int N=300005,E=524288;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int n,m,p,M;
int i,j,k,a,b,c,d;
long long dp[4][105][105][105],C[105][105],f[105][10005];
long long u[105][105][105],v[105][105][105];
long long x[105][105][105],y[105][105][105];
int main()
{
	scanf("%d %d %d %d",&n,&m,&p,&M);
	f[0][0]=1;
	for(i=1;i<=p;++i)
	{
		f[i][0]=1;
		for(j=1;j<=n*m;++j)
			f[i][j]=f[i][j-1]*i%M;
	}
	for(i=0;i<=100;++i)
	{
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;
	}
	for(a=1;a<=p;++a)
		for(b=0;b<=100;++b)
			for(i=0;i<=100;++i)
			{
				u[a][b][i]=f[a][(n-b)*i]*f[p-a][b*i]%M;
				v[a][b][i]=f[a][(m-b)*i]*f[p-a][b*i]%M;
				x[a][b][i]=f[a][(n-b)*i]*f[p-a+1][b*i]%M;
				y[a][b][i]=f[a][(m-b)*i]*f[p-a+1][b*i]%M;
			}
	dp[0][p+1][n][m]=1;
	for(a=p;a>=1;--a)
		for(b=n;b>=0;--b)
			for(c=m;c>=0;--c)
			{
				long long s=0;
				for(i=0;i+c<=m;++i)
					s=(s+(i&1?u[a][b][i]:-u[a][b][i])*C[m-c][i]%M*dp[0][a+1][b][c+i])%M;
				dp[3][a][b][c]=s;
				s=0;
				for(i=0;i+b<=n;++i)
					s=(s+(i&1?v[a][c][i]:-v[a][c][i])*C[n-b][i]%M*dp[3][a][b+i][c])%M;
				dp[2][a][b][c]=s;
				s=0;
				for(i=0;i+c<=m;++i)
					s=(s+x[a][b][i]*C[m-c][i]%M*dp[2][a][b][c+i])%M;
				dp[1][a][b][c]=s;
				s=0;
				for(i=0;i+b<=n;++i)
					s=(s+y[a][c][i]*C[n-b][i]%M*dp[1][a][b+i][c])%M;
				dp[0][a][b][c]=s;
			}
	cout<<(dp[0][1][0][0]%M+M)%M;
}