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, P, f[105][105], g[105][105], fac[105], ifac[105], pw[105][10005], trans[105][105];

int power(int a, int x) {
	int ans = 1;
	for (; x; x >>= 1, a = 1ll * a * a % P)
		if (x & 1) ans = 1ll * ans * a % P;
	return ans;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &k, &P);
	for (int i = 0; i <= k; ++i)
		for (int j = pw[i][0] = 1; j <= n * m; ++j)
			pw[i][j] = 1ll * pw[i][j - 1] * i % P;
	for (int i = fac[0] = 1; i <= max(n, m); ++i) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[max(n, m)] = power(fac[max(n, m)], P - 2);
	for (int i = max(n, m); i; --i) ifac[i - 1] = 1ll * ifac[i] * i % P;
	f[0][0] = 1;
	for (int i = 1; i <= k; ++i) {
		for (int b = 0; b <= m; ++b)
			for (int c = 0; c <= n; ++c)
				trans[c][b] = 1ll * ifac[c] * pw[i][c * (m - b)] % P * pw[k - i + 1][c * b] % P;
		for (int a = 0; a <= n; ++a)
			for (int c = 0; a + c <= n; ++c)
				for (int b = 0; b <= m; ++b)
					g[a + c][b] = (g[a + c][b] + 1ll * f[a][b] * trans[c][b]) % P;
		memcpy(f, g, sizeof g);
		memset(g, 0, sizeof g);
		for (int a = 0; a <= n; ++a)
			for (int c = 0; c <= m; ++c) {
				int tmp = 1ll * ifac[c] * pw[i][c * (n - a)] % P * pw[k - i + 1][c * a] % P;
				for (int b = 0; b + c <= m; ++b)
					g[a][b + c] = (g[a][b + c] + 1ll * f[a][b] * tmp) % P;
			}
		memcpy(f, g, sizeof g);
		memset(g, 0, sizeof g);
		for (int b = 0; b <= m; ++b)
			for (int c = 0; c <= n; ++c)
				trans[c][b] = 1ll * ifac[c] * pw[i][c * (m - b)] % P * pw[k - i][c * b] * (c & 1 ? -1 : 1) % P;
		for (int a = 0; a <= n; ++a)
			for (int c = 0; a + c <= n; ++c)
				for (int b = 0; b <= m; ++b)
					g[a + c][b] = (g[a + c][b] + 1ll * f[a][b] * trans[c][b]) % P;
		memcpy(f, g, sizeof g);
		memset(g, 0, sizeof g);
		for (int a = 0; a <= n; ++a)
			for (int c = 0; c <= m; ++c) {
				int tmp = 1ll * ifac[c] * pw[i][c * (n - a)] % P * pw[k - i][c * a] * (c & 1 ? -1 : 1) % P;
				for (int b = 0; b + c <= m; ++b)
					g[a][b + c] = (g[a][b + c] + 1ll * f[a][b] * tmp) % P;
			}
		memcpy(f, g, sizeof g);
		memset(g, 0, sizeof g);
	}
	int ans = 1ll * f[n][m] * fac[n] % P * fac[m] % P;
	printf("%d\n", (ans + P) % P);
	return 0;
}