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;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=109;
	int mod;
	inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}

	int cur,pre,f[2][N][N],n,m,K,C[N][N],pw[N][N*N];
	int main(){
		n=read<int>(),m=read<int>(),K=read<int>(),mod=read<int>();
		pw[0][0]=C[0][0]=1;
		for(int i=1;i<=max(n,m);i++){
			C[i][0]=1;
			for(int j=1;j<=i;j++) C[i][j]=add(C[i-1][j-1],C[i-1][j]);
		}for(int i=1;i<=K;i++){
			pw[i][0]=1;
			for(int j=1;j<=max(n,m);j++) pw[i][j]=1LL*pw[i][j-1]*i%mod;
		}

		f[0][0][0]=1;
		for(int t=1;t<=K;t++){
			pre=cur,cur^=1;
			for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[cur][i][j]=0;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++){
					int tmp=1LL*pw[t][m-j]*pw[K-t+1][j]%mod,omega=f[pre][i][j];
					for(int k=0;omega && k+i<=n;k++,omega=1LL*omega*tmp%mod)
						f[cur][i+k][j]=(1LL*omega*C[n-i][k]+f[cur][i+k][j])%mod;
				}
			
			pre=cur,cur^=1;
			for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[cur][i][j]=0;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++){
					int tmp=1LL*pw[t][n-i]*pw[K-t+1][i]%mod,omega=f[pre][i][j];
					for(int k=0;omega && k+j<=m;k++,omega=1LL*omega*tmp%mod)
						f[cur][i][j+k]=(1LL*omega*C[m-j][k]+f[cur][i][j+k])%mod;
				}
			
			pre=cur,cur^=1;
			for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[cur][i][j]=0;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++){
					int tmp=1LL*pw[t][m-j]*pw[K-t][j]%mod,omega=f[pre][i][j];
					for(int k=0;omega && k+i<=n;k++,omega=1LL*omega*tmp%mod)
						if(k&1) f[cur][i+k][j]=(1LL*(mod-omega)*C[n-i][k]+f[cur][i+k][j])%mod;
						else f[cur][i+k][j]=(1LL*omega*C[n-i][k]+f[cur][i+k][j])%mod;
				}
			
			pre=cur,cur^=1;
			for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[cur][i][j]=0;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++){
					int tmp=1LL*pw[t][n-i]*pw[K-t][i]%mod,omega=f[pre][i][j];
					for(int k=0;omega && k+j<=m;k++,omega=1LL*omega*tmp%mod)
						if(k&1) f[cur][i][j+k]=(1LL*(mod-omega)*C[m-j][k]+f[cur][i][j+k])%mod;
						else f[cur][i][j+k]=(1LL*omega*C[m-j][k]+f[cur][i][j+k])%mod;
				}
		}
		printf("%d\n",f[cur][n][m]);
		return 0;
	}
}
int main(){
#ifdef my
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	return run::main();
}