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;
int n, m, k, mod, dp[105][105][105][2], coef[105][105][105][2], C[105][105];
inline void Add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}
inline int qp(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res;
}
int main() {
	scanf("%d%d%d%d", &n, &m, &k, &mod);
	for (int i = C[0][0] = 1; i <= 100; i++) {
		for (int j = C[i][0] = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	for (int i = 1; i <= k; i++) {
		for (int c = 0; c <= m; c++) {
			int tmp = 1ll * (qp(i, m - c) - qp(i - 1, m - c) + mod) * qp(k - i + 1, c) % mod;
			for (int r = 0, pw = 1; r <= n; r++, pw = 1ll * pw * tmp % mod) {
				coef[i][r][c][0] = pw;
			}
		}
		for (int r = 0; r <= n; r++) {
			int tmp = 1ll * (qp(k - i + 1, r) - qp(k - i, r) + mod) * qp(i, n - r) % mod;
			for (int c = 0, pw = 1; c <= m; c++, pw = 1ll * pw * tmp % mod) {
				coef[i][r][c][1] = pw;
			}
		}
	}
	dp[0][0][0][1] = 1;
	for (int i = 1; i <= k; i++) {
		for (int r = 0; r <= n; r++) {
			for (int c = 0; c <= m; c++) {
				if (dp[i - 1][r][c][1]) {
					int t = dp[i - 1][r][c][1];
					for (int l = 0; l <= n - r; l++) {
						Add(dp[i][r + l][c][0], 1ll * t * C[n - r][l] % mod * coef[i][l][c][0] % mod);
					}
				}
				if (dp[i][r][c][0]) {
					int t = dp[i][r][c][0];
					for (int l = 0; l <= m - c; l++) {
						Add(dp[i][r][c + l][1], 1ll * t * C[m - c][l] % mod * coef[i][r][l][1] % mod);
					}
				}
			}
		}
	}
	printf("%d\n", dp[k][n][m][1]);
	return 0;
}