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 <cstring>
#include <iostream>

const int N = 100 + 3;

int n, m, k, mod;
int h[2][N][N], (*f)[N] = h[0], (*g)[N] = h[1];
int bin[N][N], pow[N][N];

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d%d%d%d", &n, &m, &k, &mod);
	if (n < m) std::swap(n, m);
	for (int i = 0; i <= std::max(n, k); ++i)
		for (int j = bin[i][0] = 1; j <= i; ++j)
			bin[i][j] = (bin[i - 1][j - 1] + bin[i - 1][j]) % mod;
	for (int i = 0; i <= std::max(n, k); ++i)
		for (int j = pow[i][0] = 1; j <= std::max(n, k); ++j)
			pow[i][j] = 1ll * pow[i][j - 1] * i % mod;
	f[0][0] = 1;
	for (int t = 0; t < k; ++t) {
		auto clear = []() {
			for (int i = 0; i <= n; ++i) memset(f[i], 0, sizeof(int) * (m + 1));
		};
		std::swap(f, g), clear();
		for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) {
			if (!g[i][j]) continue;
			int x = 1, y = 1ll * pow[t + 1][m - j] * pow[k - t][j] % mod;
			for (int l = 0; i + l <= n; ++l, x = 1ll * x * y % mod)
				f[i + l][j] = (f[i + l][j] + 1ll * bin[n - i][l] * x % mod * g[i][j]) % mod;
		}

		std::swap(f, g), clear();
		for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) {
			if (!g[i][j]) continue;
			int x = 1, y = 1ll * pow[t + 1][n - i] * pow[k - t][i] % mod;
			for (int l = 0; j + l <= m; ++l, x = 1ll * x * y % mod)
				f[i][j + l] = (f[i][j + l] + 1ll * bin[m - j][l] * x % mod * g[i][j]) % mod;
		}

		std::swap(f, g), clear();
		for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) {
			if (!g[i][j]) continue;
			int x = 1, y = -1ll * pow[t + 1][m - j] * pow[k - t - 1][j] % mod;
			for (int l = 0; i + l <= n; ++l, x = 1ll * x * y % mod)
				f[i + l][j] = (f[i + l][j] + 1ll * bin[n - i][l] * x % mod * g[i][j]) % mod;
		}

		std::swap(f, g), clear();
		for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) {
			if (!g[i][j]) continue;
			int x = 1, y = -1ll * pow[t + 1][n - i] * pow[k - t - 1][i] % mod;
			for (int l = 0; j + l <= m; ++l, x = 1ll * x * y % mod)
				f[i][j + l] = (f[i][j + l] + 1ll * bin[m - j][l] * x % mod * g[i][j]) % mod;
		}
	}
	printf("%d", (f[n][m] + mod) % mod);

	return 0;
}