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>
using namespace std;

const int _ = 103;
int dp[_][_][_][2] , C[_][_] , coef[_][_][_][2] , N , M , K , D;

int poww(long long a , int b){
	int times = 1;
	while(b){if(b & 1) times = times * a % D; a = a * a % D; b >>= 1;}
	return times;
}

int main(){
	cin >> N >> M >> K >> D;
	for(int i = 0 ; i <= max(N , M) ; ++i){
		C[i][0] = 1;
		for(int j = 1 ; j <= i ; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % D;
	}

	for(int k = 0 ; k < K ; ++k)
		for(int i = 0 ; i <= M ; ++i)
			for(int j = 0 ; j <= N ; ++j){
				coef[k][i][j][0] = 1ll * poww(K - k , i) * (poww(k + 1 , M - i) - poww(k , M - i) + D) % D;
				coef[k][i][j][1] = 1ll * (poww(K - k , j) - poww(K - k - 1 , j) + D) * poww(k + 1 , N - j) % D;
			}
					
	dp[0][0][0][0] = 1;
	for(int k = 0 ; k < K ; ++k){
		for(int p = 0 ; p <= M ; ++p)
			for(int q = 0 ; q <= N ; ++q)
				if(dp[k][p][q][0])
					for(int tms = 1 , m = 0 ; m + q <= N ; ++m , tms = 1ll * tms * coef[k][p][q][0] % D)
						dp[k][p][q + m][1] = (dp[k][p][q + m][1] + 1ll * dp[k][p][q][0] * tms % D * C[N - q][m]) % D;
		for(int p = 0 ; p <= M ; ++p)
			for(int q = 0 ; q <= N ; ++q)
				if(dp[k][p][q][1])
					for(int tms = 1 , m = 0 ; m + p <= M ; ++m , tms = 1ll * tms * coef[k][p][q][1] % D)
						dp[k + 1][p + m][q][0] = (dp[k + 1][p + m][q][0] + 1ll * dp[k][p][q][1] * tms % D * C[M - p][m]) % D;
	}
	
	cout << dp[K][M][N][0];
	return 0;
}