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 N 101
typedef long long ll;
int n, m, k, d;

int expmod(int a, int b) {
	int rlt = 1;
	for (a %= d; b; b >>= 1, a = 1ll * a * a % d) if (b&1) rlt = 1ll * rlt * a % d;
	return rlt;
}

int C[N][N];

void comb() {
	C[0][0] = 1;
	for (int i = 1; i < N; i ++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j ++) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % d;
	}
}

int dp[2][N][N];

void add(int &a, ll b) {
	a = (a + b) % d;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k>>d;
	comb();
	int u = 0, v = 1;
	dp[u][n][m] = 1;
	for (int i = 1; i <= k; i ++) {
		memset(dp[v], 0, sizeof dp[v]);
		for (int r = 0; r <= n; r ++) {
			for (int c = 0; c <= m; c ++) if (dp[u][r][c]) {
				int fa = expmod(i, c) - expmod(i - 1, c) + d, fb = expmod(k - i + 1, m - c);
				for (int x = 0, ca = 1, cb = 1; x <= r; x ++, ca = 1ll * ca * fa % d, cb = 1ll * cb * fb % d) {
					add(dp[v][r-x][c], 1ll * C[r][x] * ca % d * cb % d * dp[u][r][c]);
				}
			}
		}
		swap(u, v);
		memset(dp[v], 0, sizeof dp[v]);
		for (int r = 0; r <= n; r ++) {
			for (int c = 0; c <= m; c ++) if (dp[u][r][c]) {
				int fa = expmod(k - i + 1, n - r) - expmod(k - i, n - r) + d, fb = expmod(i, r);
				for (int y = 0, ca = 1, cb = 1; y <= c; y ++, ca = 1ll * ca * fa % d, cb = 1ll * cb * fb % d) {
					add(dp[v][r][c-y], 1ll * C[c][y] * ca % d * cb % d * dp[u][r][c]);
				}
			}
		}
		swap(u, v);
	}
	cout<<dp[u][0][0];
}