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>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int N = 105;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

namespace ModCalculator {
	int MOD;
	inline void Inc(int &x, int y) {
		x += y; if (x >= MOD) x -= MOD;
	}
	inline void Dec(int &x, int y) {
		x -= y; if (x < 0) x += MOD;
	}
	inline int Mul(int x, int y) {
		return 1LL * x * y % MOD;
	}
	inline int Mul(int x, int y, int z) {
		return 1LL * x * y % MOD * z % MOD;
	}
}
using namespace ModCalculator;

inline int ksm(int x, int k) {
	int ret = 1;
	while (k) {
		if (k & 1) ret = Mul(ret, x);
		x = Mul(x, x);
		k >>= 1;
	}
	return ret;
}

int n, m, K;
int fac[N], finv[N], pw[N][N * N];
int dp[2][N][N], g[N][N];

void init() {
	read(n); read(m); read(K); read(MOD);
	if (n < m) swap(n, m);
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = Mul(fac[i - 1], i);
	}
	finv[n] = ksm(fac[n], MOD - 2);
	for (int i = n - 1; i >= 0; --i) {
		finv[i] = Mul(finv[i + 1], i + 1);
	}
	for (int i = 0, r = n * m; i <= K; ++i) {
		pw[i][0] = 1;
		for (int j = 1; j <= r; ++j) {
			pw[i][j] = Mul(pw[i][j - 1], i);
		}
	}
}

void solve() {
	int cur = 0, pre = 1;
	dp[0][0][0] = 1;
	for (int i = 1; i <= K; ++i) {
		swap(pre, cur);
		mset(dp[cur], 0);
		for (int t = 0; t <= n; ++t) {
			for (int k = 0; k <= m; ++k) {
				g[t][k] = Mul(finv[t], pw[i][t * (m - k)], pw[K - i + 1][t * k]);
			}
		}
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= m; ++k) {
				for (int t = 0; t <= j; ++t) {
					Inc(dp[cur][j][k], Mul(dp[pre][j - t][k], g[t][k]));
				}
			}
		}
		
		swap(pre, cur);
		mset(dp[cur], 0);
		for (int j = 0; j <= n; ++j) {
			for (int t = 0; t <= m; ++t) {
				g[j][t] = Mul(finv[t], pw[i][t * (n - j)], pw[K - i + 1][t * j]);
			}
		}
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= m; ++k) {
				for (int t = 0; t <= k; ++t) {
					Inc(dp[cur][j][k], Mul(dp[pre][j][k - t], g[j][t]));
				}
			}
		}
		
		swap(pre, cur);
		mset(dp[cur], 0);
		for (int t = 0; t <= n; ++t) {
			for (int k = 0; k <= m; ++k) {
				g[t][k] = Mul(finv[t], pw[i][t * (m - k)], pw[K - i][t * k]);
				if (t & 1) g[t][k] = MOD - g[t][k];
			}
		}
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= m; ++k) {
				for (int t = 0; t <= j; ++t) {
					Inc(dp[cur][j][k], Mul(dp[pre][j - t][k], g[t][k]));
				}
			}
		}
		
		swap(pre, cur);
		mset(dp[cur], 0);
		for (int j = 0; j <= n; ++j) {
			for (int t = 0; t <= m; ++t) {
				g[j][t] = Mul(finv[t], pw[i][t * (n - j)], pw[K - i][t * j]);
				if (t & 1) g[j][t] = MOD - g[j][t];
			}
		}
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= m; ++k) {
				for (int t = 0; t <= k; ++t) {
					Inc(dp[cur][j][k], Mul(dp[pre][j][k - t], g[j][t]));
				}
			}
		}
	}
	printf("%d\n", Mul(dp[pre][n][m], fac[n], fac[m]));
}

int main() {
	init();
	solve();
	return 0;
}