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 fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define add(x,y)(x=((ll)y+x)%mo)
#define ll long long
using namespace std;
const int N=105;
int n,m,k,mo,v,A;
int g[N][N],g2[N][N];
int f[N][N][N][2];
int jc[N],ny[N];
int ksm(int x,int y){
	int t=1;
	for(;y;y>>=1,x=(ll)x*x%mo)if(y&1)t=(ll)t*x%mo;
	return t;
}
int main(){
	cin>>n>>m>>k>>mo;
	A=max(max(n,m),k);
	jc[0]=1;
	fo(i,1,A)jc[i]=(ll)jc[i-1]*i%mo;
	ny[A]=ksm(jc[A],mo-2);
	fd(i,0,A-1)ny[i]=(ll)ny[i+1]*(i+1)%mo;
	f[0][0][0][0]=1;
	fo(i,0,A){
		g[i][0]=1;
		fo(j,1,A)g[i][j]=(ll)g[i][j-1]*i%mo;
		if(i)
			fo(j,0,A)g2[i][j]=(g[i][j]-g[i-1][j]+mo)%mo;
	}
	fo(i,0,n)fo(j,0,m)
		fo(l,0,k){
			if(v=f[i][j][l][1]){
				int x=1,xs=(ll)g[l][n-i]*g2[k-l+1][i]%mo;
				fo(j0,0,m-j){
					add(f[i][j+j0][l][0],v*x%mo*ny[j0]);
					x=(ll)x*xs%mo;
				}
			}
			
			if((v=f[i][j][l][0])&&l<k){
				int x=1,xs=(ll)g2[l+1][m-j]*g[k-(l+1)+1][j]%mo;
				fo(i0,0,n-i){
					add(f[i+i0][j][l+1][1],v*x%mo*ny[i0]);
					x=(ll)x*xs%mo;
				}
			}
		}
	cout<<(ll)f[n][m][k][0]*jc[n]%mo*jc[m]%mo;
}