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 <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
int n, m, k, P, dp[MAXN][MAXN][MAXN][2];
int binom[MAXN][MAXN], coef[MAXN][MAXN][MAXN][2];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int main()
{
	scanf("%d%d%d%d", &n, &m, &k, &P);
	dp[1][0][0][0] = 1;
	for (int i = 0; i <= max(n, m); i++) {
		binom[i][0] = 1;
		for (int j = 1; j <= i; j++)
			binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % P;
	}
	for (int t = 1; t <= k; t++)
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			int tmp = (power(t, m - i) - power(t - 1, m - i) + P) % P;
			tmp = 1ll * tmp * power(k - t + 1, i) % P;
			coef[t][i][j][0] = power(tmp, j);
		}
	}
	for (int t = 1; t <= k; t++)
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			int tmp = (power(k - t + 1, i) - power(k - t, i) + P) % P;
			tmp = 1ll * tmp * power(t, n - i) % P;
			coef[t][i][j][1] = power(tmp, j);
		}
	}
	for (int t = 1; t <= k; t++) {
		for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++) {
			int tmp = dp[t][i][j][0];
			for (int k = 0; i + k <= n; k++)
				update(dp[t][i + k][j][1], 1ll * tmp * binom[n - i][k] % P * coef[t][j][k][0] % P);
			tmp = dp[t][i][j][1];
			for (int k = 0; j + k <= m; k++)
				update(dp[t + 1][i][j + k][0], 1ll * tmp * binom[m - j][k] % P * coef[t][i][k][1] % P);
		}
	}
	printf("%d\n", dp[k + 1][n][m][0]);
}