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;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int MOD;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(const ll& x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
};
bool done[105][105][105][2];
Mint dp[105][105][105][2];
int N, M, K;
const int MAXN = 105;
Mint binom[MAXN][MAXN];
Mint power[MAXN][MAXN * MAXN];
Mint cache0[105][105][105], cache1[105][105][105];
Mint solve(int i, int j, int k, int t) {
	if (i == N && j == M) return 1;
	if (k == K + 1) return 0;
	Mint& ret = dp[i][j][k][t];
	if (done[i][j][k][t]) return ret;
	done[i][j][k][t] = true;
	ret = 0;
	if (t == 0) {
		ret += solve(i, j, k, 1);
		for (int r = 1; r <= N - i; ++r) {
			ret += cache0[k][j][r] * binom[N - i][r] * solve(i + r, j, k, 1);
		}
	} else {
		ret += solve(i, j, k + 1, 0);
		for (int c = 1; c <= M - j; ++c) {
			if (!i) break;
			if (c == M - j && i != N) continue;
			ret += cache1[k][i][c] * binom[M - j][c] * solve(i, j + c, k + 1, 0);
		}
	}
	return ret;
}
int main() {
	scanf("%d%d%d%d", &N, &M, &K, &MOD);
	for (int i = 0; i < MAXN; ++i)
		for (int j = 0; j <= i; ++j)
			if (!j || j == i) binom[i][j] = 1;
			else binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
	for (int i = 0; i < MAXN; ++i) {
		power[i][0] = 1;
		for (int j = 1; j < MAXN * MAXN; ++j) {
			power[i][j] = power[i][j - 1] * i;
		}
	}
	for (int k = 1; k <= K; ++k) {
		for (int j = 0; j <= M; ++j) {
			Mint mult = 1, base = power[k][M - j] - power[k - 1][M - j];
			for (int r = 0; r <= N; ++r) {
				cache0[k][j][r] = mult * power[K - k + 1][j * r];
				mult *= base;
			}
		}
		for (int i = 1; i <= N; ++i) {
			Mint mult = 1, base = power[K - k + 1][i] - power[K - k][i];
			for (int c = 0; c <= M; ++c) {
				cache1[k][i][c] = mult * power[k][(N - i) * c];
				mult *= base;
			}
		}
	}
	Mint ans = solve(0, 0, 1, 0);
	printf("%d\n", ans.val);
}