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 N=110;

int gi() {
	int x=0,o=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,m,t,mod,f[N][N][N][2],g[N][N][N][2],C[N][N];

int qpow(int a,int b) {
	int ret=1;
	while(b) {
		if(b&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return ret;
}

int main() {
	n=gi(),m=gi(),t=gi(),mod=gi();
	f[1][0][0][0]=1;
	for(int i=0;i<=n||i<=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<=t;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=m;k++) {
				int tmp=(qpow(i,m-k)-qpow(i-1,m-k)+mod)%mod;
				tmp=1ll*tmp*qpow(t-i+1,k)%mod;
				g[i][j][k][0]=qpow(tmp,j);
			}
	for(int i=1;i<=t;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=n;k++) {
				int tmp=(qpow(t-i+1,k)-qpow(t-i,k)+mod)%mod;
				tmp=1ll*tmp*qpow(i,n-k)%mod;
				g[i][j][k][1]=qpow(tmp,j);
			}
	for(int i=1;i<=t;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=m;k++) {
				if(f[i][j][k][0])
					for(int l=0;l+j<=n;l++)
						f[i][j+l][k][1]=(f[i][j+l][k][1]+1ll*f[i][j][k][0]*g[i][l][k][0]%mod*C[n-j][l])%mod;
				if(f[i][j][k][1])
					for(int l=0;l+k<=m;l++)
						f[i+1][j][k+l][0]=(f[i+1][j][k+l][0]+1ll*f[i][j][k][1]*g[i][l][j][1]%mod*C[m-k][l])%mod;
			}
	cout<<f[t+1][n][m][0];
	return 0;
}