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>
int N,M,K,D;
int C[105][105],pw[105][10205],tmp1[105][105][105],tmp2[105][105][105],tmp3[105][105][105],tmp4[105][105][105],f[105][4][105][105];
int main(){
	scanf("%d%d%d%d",&N,&M,&K,&D);
	f[K][3][N][M]=1;
	for(int i=0;i<=101;i++){
		for(int j=*C[i]=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%D;
		for(int j=*pw[i]=1;j<=10201;j++)pw[i][j]=1ll*pw[i][j-1]*i%D;
	}
	for(int i=1;i<=K;i++){
		for(int j=0;j<=100;j++){
			for(int k=0;k<=M;k++){
				tmp1[i][j][k]=pw[K-i][j*k]*1ll*pw[i][j*(M-k)]%D;
				tmp2[i][j][k]=pw[K-i+1][j*k]*1ll*pw[i][j*(M-k)]%D;
			}
			for(int k=0;k<=N;k++){
				tmp3[i][j][k]=pw[K-i][j*k]*1ll*pw[i][j*(N-k)]%D;
				tmp4[i][j][k]=pw[K-i+1][j*k]*1ll*pw[i][j*(N-k)]%D;
			}
		}
	}
	for(int x=K;x;x--){
		for(int ty=4;ty--;){
			for(int i=0;i<=N;i++){
				for(int j=0,F;j<=M;j++)if(F=f[x][ty][i][j]){
					if(ty==3){
						for(int y=0;y<=i;y++)
							f[x][2][i-y][j]=(f[x][2][i-y][j]+1ll*F*(y&1?D-C[i][y]:C[i][y])%D*tmp1[x][y][j])%D;
					}
					if(ty==2){
						for(int y=0;y<=j;y++)
							f[x][1][i][j-y]=(f[x][1][i][j-y]+1ll*F*(y&1?D-C[j][y]:C[j][y])%D*tmp3[x][y][i])%D;
					}
					if(ty==1){
						for(int y=0;y<=i;y++)
							f[x][0][i-y][j]=(f[x][0][i-y][j]+1ll*F*C[i][y]%D*tmp2[x][y][j])%D;
					}
					if(ty==0){
						for(int y=0;y<=j;y++)
							f[x-1][3][i][j-y]=(f[x-1][3][i][j-y]+1ll*F*C[j][y]%D*tmp4[x][y][i])%D;
					}
				}
			}
		}
	}
	printf("%d\n",f[0][3][0][0]);
}