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>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define y1 fdhjksa
using namespace std;
const int N=105;
int n,m,k,mo;
int inv[N],Inv[N];
int P[N][N*N],IP[N][N*N];
int f[N][N][N],g[N][N],h[N][N];
int main(){
	scanf("%d%d%d%d",&n,&m,&k,&mo);
	inv[0]=inv[1]=Inv[0]=1;
	For(i,2,N-1) inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
	For(i,0,k) P[i][0]=IP[i][0]=1;
	For(i,0,k) For(j,1,n*m) P[i][j]=1ll*P[i][j-1]*i%mo;
	For(i,0,k) For(j,1,n*m) IP[i][j]=1ll*IP[i][j-1]*inv[i]%mo;
	For(i,1,N-1) Inv[i]=1ll*Inv[i-1]*inv[i]%mo;
	f[0][0][0]=1;
	For(i,1,::k){
		For(j,0,n) For(k,0,m) g[j][k]=1ll*P[i][(n-j)*(m-k)]*f[i-1][j][k]%mo;
		For(j,0,n) For(k,0,m) h[j][k]=0;
		For(k,0,m) For(jj,0,n){
			int tr=1ll*Inv[jj]*P[::k-i+1][jj*k]%mo;
			For(j,0,n-jj) h[j+jj][k]=(h[j+jj][k]+1ll*g[j][k]*tr)%mo;
		}
		For(j,0,n) For(k,0,m) g[j][k]=0;
		For(j,0,n) For(kk,0,m){
			int tr=1ll*Inv[kk]*P[::k-i+1][j*kk]%mo;
			For(k,0,m-kk) g[j][k+kk]=(g[j][k+kk]+1ll*h[j][k]*tr)%mo;
		}
		For(j,0,n) For(k,0,m) h[j][k]=0;
		For(k,0,m) For(jj,0,n){
			int tr=1ll*(jj&1?mo-Inv[jj]:Inv[jj])*P[::k-i][jj*k]%mo;
			For(j,0,n-jj) h[j+jj][k]=(h[j+jj][k]+1ll*g[j][k]*tr)%mo;
		}
		For(j,0,n) For(k,0,m) g[j][k]=0;
		For(j,0,n) For(kk,0,m){
			int tr=1ll*(kk&1?mo-Inv[kk]:Inv[kk])*P[::k-i][j*kk]%mo;
			For(k,0,m-kk) g[j][k+kk]=(g[j][k+kk]+1ll*h[j][k]*tr)%mo;
		}
		For(j,0,n) For(k,0,m)
			f[i][j][k]=1ll*g[j][k]*IP[i][(n-j)*(m-k)]%mo;
	}
	int ans=f[k][n][m];
	For(i,1,n) ans=1ll*ans*i%mo;
	For(i,1,m) ans=1ll*ans*i%mo;
	printf("%d\n",ans);
}