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 rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int MOD;

int power(int x, int t)
{
	int ret = 1;
	while(t > 0) {
		if(t & 1) ret = 1LL * ret * x % MOD;
		x = 1LL * x * x % MOD;
		t >>= 1;
	}
	return ret;
}

int n, m, k;
int fac[105], ifac[105];
int dp[105][105];

int pw[10005];
void mul_dp(int x, int dir)
{
	pw[0] = 1;
	rep1(i, n * m) pw[i] = 1LL * pw[i - 1] * x % MOD;
	
	if(dir == -1) for(int i = 0; i <= n; i ++) for(int j = 0; j <= m; j ++)
	dp[i][j] = 1LL * dp[i][j] * pw[n * m - (n - i) * (m - j)] % MOD;
	else for(int i = 0; i <= n; i ++) for(int j = 0; j <= m; j ++)
	dp[i][j] = 1LL * dp[i][j] * pw[i * j] % MOD;
}

void conv_dp(int coef)
{
	for(int i = n; i >= 0; i --) for(int j = 0; j <= m; j ++)
	rep(i0, i) if(coef == -1 && (i - i0 & 1))
	dp[i][j] = (dp[i][j] + 1LL * dp[i0][j] * (MOD - ifac[i - i0])) % MOD;
	else dp[i][j] = (dp[i][j] + 1LL * dp[i0][j] * ifac[i - i0]) % MOD;
	
	for(int i = 0; i <= n; i ++) for(int j = m; j >= 0; j --)
	rep(j0, j) if(coef == -1 && (j - j0 & 1))
	dp[i][j] = (dp[i][j] + 1LL * dp[i][j0] * (MOD - ifac[j - j0])) % MOD;
	else dp[i][j] = (dp[i][j] + 1LL * dp[i][j0] * ifac[j - j0]) % MOD;
}

int main()
{
	scanf("%d%d%d%d", &n, &m, &k, &MOD);
	
	fac[0] = 1;
	rep1(i, 100) fac[i] = 1LL * fac[i - 1] * i % MOD;
	rep(i, 101) ifac[i] = power(fac[i], MOD - 2);
	
	dp[0][0] = 1;
	
	for(int i = k; i >= 1; i --) {
		mul_dp(power(i, MOD - 2), 1);
		mul_dp(power((k - i + 1), MOD - 2), -1);
		if(i != k) {
			mul_dp(1LL * (k - i + 1) * power(k - i, MOD - 2) % MOD, -1);
			conv_dp(-1);
			mul_dp(1LL * (k - i) * power(k - i + 1, MOD - 2) % MOD, -1);
		}
		conv_dp(1);
		mul_dp((k - i + 1), -1);
		mul_dp(i, 1);
	}
	
	printf("%d\n", 1LL * fac[n] * fac[m] % MOD * dp[n][m] % MOD);
	return 0;
}