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 <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=105;

int n,m,k,Mo,C[N][N],f[N][N][N][2];

int pwr(int x,int y) {
	int z=1;
	for(;y;y>>=1,x=(ll)x*x%Mo)
		if (y&1) z=(ll)z*x%Mo;
	return z;
}

int main() {
	scanf("%d%d%d%d",&n,&m,&k,&Mo);
	fo(i,0,max(n,m)) {
		C[i][0]=1;
		fo(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mo;
	}
	f[0][0][0][0]=1;
	fo(x,0,k-1) 
		fo(i,0,n) fo(j,0,m) {
			int ret=1,cnt=(pwr(x+1,m-j)-pwr(x,m-j))%Mo;
			cnt=(ll)cnt*pwr(k-x,j)%Mo;
			fo(l,0,n-i) {
				(f[x][i+l][j][1]+=(ll)f[x][i][j][0]*C[n-i][l]%Mo*ret%Mo)%=Mo;
				ret=(ll)ret*cnt%Mo;
			}
			ret=1;cnt=(pwr(k-x,i)-pwr(k-x-1,i))%Mo;
			cnt=(ll)cnt*pwr(x+1,n-i)%Mo;
			fo(l,0,m-j) {
				(f[x+1][i][j+l][0]+=(ll)f[x][i][j][1]*C[m-j][l]%Mo*ret%Mo)%=Mo;
				ret=(ll)ret*cnt%Mo;
			}
		}
	printf("%d\n",(f[k][n][m][0]+Mo)%Mo);
	return 0;
}