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;
int fac[10005],inv[10005],fac_inv[10005];
void init(){
	fac[0]=fac_inv[0]=inv[1]=1;
	for(int i=1;i<=10000;++i){
		fac[i]=1ll*fac[i-1]*i%MOD;
		if(i>1) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
		fac_inv[i]=1ll*fac_inv[i-1]*inv[i]%MOD;
	}
}
inline int fpow(int x,int n,int ret=1){
	for(;n;n>>=1,x=1ll*x*x%MOD)
		n&1?ret=1ll*ret*x%MOD:0;
	return ret;
}
int f[105][105],g[105][105],t[105];
void mul1(){
	for(int x=n;x>=0;--x)
	for(int y=0;y<=m;++y){
		f[x][y]=1ll*f[x][y]*t[0]%MOD;
		for(int i=0;i<x;++i)
			f[x][y]=(f[x][y]+1ll*f[i][y]*t[x-i])%MOD;
	}
}
void mul2(){
	for(int x=0;x<=n;++x)
	for(int y=m;y>=0;--y){
		f[x][y]=1ll*f[x][y]*t[0]%MOD;
		for(int i=0;i<y;++i)
			f[x][y]=(f[x][y]+1ll*f[x][i]*t[y-i])%MOD;
	}
}
int pw1[10005],pw2[10005],pw3[10005];
int main(){
	scanf("%d%d%d%d",&n,&m,&k,&MOD);
	init();
	f[0][0]=1;
	for(int kk=1;kk<=k;++kk){
		int a=k-kk+1,b=k-kk,c=kk;
		pw1[0]=pw2[0]=pw3[0]=1;
		for(int i=1;i<=n*m;++i){
			pw1[i]=1ll*pw1[i-1]*(k-kk+1)%MOD;
			pw2[i]=1ll*pw2[i-1]*(k-kk)%MOD;
			pw3[i]=1ll*pw3[i-1]*kk%MOD;
		}
		for(int x=0;x<=n;++x)
		for(int y=0;y<=m;++y)
			f[x][y]=1ll*f[x][y]*fpow(pw1[x*y],MOD-2)%MOD*pw3[x*y]%MOD;
		for(int i=0;i<=n;++i) 
			t[i]=1ll*fac_inv[i]*pw3[i*m]%MOD;
		mul1();
		for(int i=0;i<=m;++i) 
			t[i]=1ll*fac_inv[i]*pw3[i*n]%MOD;
		mul2();
		if(k==kk){
			for(int x=0;x<=n;++x)
			for(int y=0;y<=m;++y)
				f[x][y]=1ll*f[x][y]*pw1[x*y]%MOD*fpow(pw3[x*y],MOD-2)%MOD;
			break;
		}
		for(int x=0;x<=n;++x)
		for(int y=0;y<=m;++y)
			f[x][y]=1ll*f[x][y]*pw1[x*y]%MOD*fpow(pw2[x*y],MOD-2)%MOD;
		for(int i=0;i<=n;++i) 
			t[i]=1ll*fac_inv[i]*pw3[i*m]%MOD*(i&1?MOD-1:1)%MOD;
		mul1();
		for(int i=0;i<=m;++i) 
			t[i]=1ll*fac_inv[i]*pw3[i*n]%MOD*(i&1?MOD-1:1)%MOD;
		mul2();
		for(int x=0;x<=n;++x)
		for(int y=0;y<=m;++y)
			f[x][y]=1ll*f[x][y]*pw2[x*y]%MOD*fpow(pw3[x*y],MOD-2)%MOD;
	}
	int ans=1ll*f[n][m]*fac[n]%MOD*fac[m]%MOD;
	printf("%d\n",ans);
	return 0;
}