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>

const int N = 105, M = 1e4 + 5;

int n, m, K, djq, inv[N], f[N][N], C[N][N], pw[N][M], ipw[N][M];

inline void add(int &a, const int &b) {if ((a += b) >= djq) a -= djq;}

int main()
{
	std::cin >> n >> m >> K >> djq; inv[1] = 1;
	for (int i = 2; i <= K; i++) inv[i] = 1ll * (djq - djq / i) * inv[djq % i] % djq;
	f[0][0] = 1;
	for (int i = 0; i <= 100; i++) C[i][0] = 1;
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= i; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % djq;
	for (int i = 1; i <= K; i++)
	{
		pw[i][0] = ipw[i][0] = 1;
		for (int j = 1; j <= n * m; j++)
			pw[i][j] = 1ll * pw[i][j - 1] * i % djq,
				ipw[i][j] = 1ll * ipw[i][j - 1] * inv[i] % djq;
	}
	for (int T = 1; T <= K; T++)
	{
		for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
			f[i][j] = 1ll * f[i][j] * ipw[K - T + 1][i * j] % djq;
		for (int j = 0; j <= m; j++)
			for (int i = n; i >= 0; i--)
				for (int k = 0; k < i; k++)
					f[i][j] = (1ll * f[k][j] * C[n - k][i - k] + f[i][j]) % djq;
		for (int i = 0; i <= n; i++)
			for (int j = m; j >= 0; j--)
				for (int k = 0; k < j; k++)
					f[i][j] = (1ll * f[i][k] * C[m - k][j - k] + f[i][j]) % djq;
		for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
			f[i][j] = 1ll * f[i][j] * pw[K - T + 1][i * j] % djq;
		if (T < K)
		{
			for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
				f[i][j] = 1ll * f[i][j] * ipw[K - T][i * j] % djq;
			for (int j = 0; j <= m; j++)
				for (int i = n; i >= 0; i--)
					for (int k = 0; k < i; k++)
					{
						int delta = 1ll * f[k][j] * C[n - k][i - k] % djq;
						add(f[i][j], i - k & 1 ? djq - delta : delta);
					}
			for (int i = 0; i <= n; i++)
				for (int j = m; j >= 0; j--)
					for (int k = 0; k < j; k++)
					{
						int delta = 1ll * f[i][k] * C[m - k][j - k] % djq;
						add(f[i][j], j - k & 1 ? djq - delta : delta);
					}
			for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
				f[i][j] = 1ll * f[i][j] * pw[K - T][i * j] % djq
					* pw[T + 1][(n - i) * (m - j)] % djq *
						ipw[T][(n - i) * (m - j)] % djq;
		}
	}
	return std::cout << f[n][m] << std::endl, 0;
}