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;
const int MAXN = 105;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, k, P, dp[MAXN][MAXN][MAXN][2];
int binom[MAXN][MAXN], coef[MAXN][MAXN][MAXN][2];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int main() {
	read(n), read(m), read(k), read(P), dp[1][0][0][0] = 1;
	for (int i = 0; i <= 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]) % P;
	}
	for (int t = 1; t <= k; t++)
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			int tmp = (power(t, m - i) - power(t - 1, m - i) + P) % P;
			tmp = 1ll * tmp * power(k - t + 1, i) % P;
			coef[t][i][j][0] = power(tmp, j);
		}
	}
	for (int t = 1; t <= k; t++)
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			int tmp = (power(k - t + 1, i) - power(k - t, i) + P) % P;
			tmp = 1ll * tmp * power(t, n - i) % P;
			coef[t][i][j][1] = power(tmp, j);
		}
	}
	for (int t = 1; t <= k; t++) {
		for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++) {
			int tmp = dp[t][i][j][0];
			for (int k = 0; i + k <= n; k++)
				update(dp[t][i + k][j][1], 1ll * tmp * binom[n - i][k] % P * coef[t][j][k][0] % P);
			tmp = dp[t][i][j][1];
			for (int k = 0; j + k <= m; k++)
				update(dp[t + 1][i][j + k][0], 1ll * tmp * binom[m - j][k] % P * coef[t][i][k][1] % P);
		}
	}
	writeln(dp[k + 1][n][m][0]);
	return 0;
}