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 meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
int (*rd)()=read<int>;

const int N=105;
int n, m, k;
u32 P, inv[N], pw[N][N*N], ipw[N][N*N], com[N][N], f[N][N], g[N][N];
void trans() {
	for(int i=0; i<=n; ++i)
		for(int j=0; j<=m; ++j) {
			g[i][j]=0;
			for(int b=0; b<=j; ++b) g[i][j]=(g[i][j]+(u64)f[i][b]*com[j][b])%P;
		}
	for(int i=0; i<=n; ++i)
		for(int j=0; j<=m; ++j) {
			f[i][j]=0;
			for(int a=0; a<=i; ++a) f[i][j]=(f[i][j]+(u64)g[a][j]*com[i][a])%P;
		}
}
int main() {
	n=rd(), m=rd(), k=rd(), P=rd();
	pw[0][0]=1;
	for(int i=1; i<=k; ++i) {
		pw[i][0]=1;
		for(int j=1; j<=n*m; ++j) pw[i][j]=(u64)pw[i][j-1]*i%P;
	}
	inv[1]=1;
	for(int i=2; i<=k; ++i) inv[i]=(u64)(P-P/i)*inv[P%i]%P;
	ipw[0][0]=1;
	for(int i=1; i<=k; ++i) {
		ipw[i][0]=1;
		for(int j=1; j<=n*m; ++j) ipw[i][j]=(u64)ipw[i][j-1]*inv[i]%P;
	}
	for(int i=0; i<=n||i<=m; ++i) {
		com[i][0]=com[i][i]=1;
		for(int j=1; j<i; ++j) com[i][j]=(com[i-1][j-1]+com[i-1][j])%P;
	}
	f[0][0]=1;
	for(int t=1; t<=k; ++t) {
		for(int i=0; i<=n; ++i)
			for(int j=0; j<=m; ++j)
				f[i][j]=(u64)f[i][j]*pw[t][(n-i)*(m-j)]%P*ipw[k-t+1][i*j]%P;
		trans();
		if(k==t) break;
		for(int i=0; i<=n; ++i)
			for(int j=0; j<=m; ++j)
				f[i][j]=(u64)(i+j&1?P-f[i][j]:f[i][j])*pw[k-t+1][i*j]%P*ipw[k-t][i*j]%P;
		trans();
		for(int i=0; i<=n; ++i)
			for(int j=0; j<=m; ++j)
				f[i][j]=(u64)(i+j&1?P-f[i][j]:f[i][j])*pw[k-t][i*j]%P*ipw[t][(n-i)*(m-j)]%P;
	}
	printf("%u\n", f[n][m]);
	return 0;
}