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 rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef double ld;
typedef vi poly;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=105;
int f[N][N][N],t[N][N],C[N][N],coef[N][N][N],po[N][N*N];
int n,m,K;

namespace{
	int P;
	int fix(int x){
		return x>=P?x-P:x;
	}
	void add(int &x,int y){
		x=(x+y>=P?x+y-P:x+y);
	}
	int mul(int x,int y){
		return (ll)x*y%P;
	}
	int power(int x,int p){
		int res=1;
		for(;p;p>>=1,x=mul(x,x))
			if(p&1)res=mul(res,x);
		return res;
	}
}

void init(){
	C[0][0]=1;
	rep(i,1,100){
		C[i][0]=1;
		rep(j,1,100)
			C[i][j]=fix(C[i-1][j-1]+C[i-1][j]);
	}
	rep(i,1,100)rep(j,0,100){
		coef[i][j][0]=1;
		coef[i][j][1]=fix(power(i,j)+P-power(i-1,j));
		rep(k,2,100)
			coef[i][j][k]=mul(coef[i][j][k-1],coef[i][j][1]);
	}
	rep(i,0,100){
		po[i][0]=1;
		rep(j,1,10000)po[i][j]=mul(po[i][j-1],i);
	}
}

int main(){
	read(n),read(m);
	read(K),read(P);
	init(),f[0][0][0]=1;
	rep(k,0,K-1){
		memset(t,0,sizeof t);
		rep(i,0,n)rep(j,0,m)
			if(f[k][i][j])
				rep(x,0,n-i){
					int cc=mul(po[K-k][j*x],coef[k+1][m-j][x]);
					add(t[i+x][j],mul(f[k][i][j],mul(C[n-i][x],cc)));
				}
		rep(i,0,n)rep(j,0,m)
			if(t[i][j])
				rep(y,0,m-j){
					int cc=mul(po[k+1][(n-i)*y],coef[K-k][i][y]);
					add(f[k+1][i][j+y],mul(t[i][j],mul(C[m-j][y],cc)));
				}
	}
	printf("%d\n",f[K][n][m]);
	return 0;
}