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 <algorithm>

typedef long long LL;
int Mod;
const int MN = 105, MK = 105;

int Binom[MN][MN], Pow[MK][MN];
int N, M, K;
int f[2][MN][MN];

int main() {
	scanf("%d%d%d%d", &N, &M, &K, &Mod);
	for (int i = 0; i <= std::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]) % Mod;
	}
	for (int i = 0; i <= K; ++i) {
		Pow[i][0] = 1;
		for (int j = 1; j <= std::max(N, M); ++j)
			Pow[i][j] = (LL)Pow[i][j - 1] * i % Mod;
	}
	int o = 0;
	f[0][0][0] = 1;
#define Z0(x) for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) f[x][i][j] = 0;
	for (int t = 1; t <= K; ++t) {
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)Pow[K - t + 1][j] * Pow[t][M - j] % Mod;
			for (int a = 0; i + a <= N; ++a, x = (LL)x * y % Mod)
				f[o ^ 1][i + a][j] = (f[o ^ 1][i + a][j] + (LL)Binom[N - i][a] * x) % Mod;
		} o ^= 1;
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)Pow[K - t + 1][i] * Pow[t][N - i] % Mod;
			for (int b = 0; j + b <= M; ++b, x = (LL)x * y % Mod)
				f[o ^ 1][i][j + b] = (f[o ^ 1][i][j + b] + (LL)Binom[M - j][b] * x) % Mod;
		} o ^= 1;
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)(Mod - Pow[K - t][j]) * Pow[t][M - j] % Mod;
			for (int c = 0; i + c <= N; ++c, x = (LL)x * y % Mod)
				f[o ^ 1][i + c][j] = (f[o ^ 1][i + c][j] + (LL)Binom[N - i][c] * x) % Mod;
		} o ^= 1;
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)(Mod - Pow[K - t][i]) * Pow[t][N - i] % Mod;
			for (int d = 0; j + d <= M; ++d, x = (LL)x * y % Mod)
				f[o ^ 1][i][j + d] = (f[o ^ 1][i][j + d] + (LL)Binom[M - j][d] * x) % Mod;
		} o ^= 1;
	}
	printf("%d\n", f[o][N][M]);
	return 0;
}