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 <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int Max_K(105);
const int Max_NM(105);

int N, M, K, MOD, Fac[Max_NM], Inv[Max_NM], F[Max_NM][Max_NM], G[2][Max_NM][Max_NM], power[Max_K][Max_NM * Max_NM];

inline int Add(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}

inline int Sub(int a, int b)
{
	return a - b < 0 ? a - b + MOD : a - b;
}

inline int Mult(int a, int b)
{
	return a * 1LL * b % MOD;
}

inline void upd(int &a, int b)
{
	a = Add(a, b);
}

inline void inc(int &a, int b)
{
	a = Sub(a, b);
}

void exgcd(int a, int b, int &x, int &y)
{
	if (b == 0)
		x = 1, y = 0;
	else
		exgcd(b, a % b, y, x), y -= x * (a / b);
}

inline int inverse(int a)
{
	int invx, invy;
	exgcd(a, MOD, invx, invy);
	return (invx % MOD + MOD) % MOD;
}

int main()
{
	scanf("%d%d%d%d", &N, &M, &K, &MOD);
	Fac[0] = 1;
	for (int i = 1;i <= max(N, M);++i)
		Fac[i] = Mult(Fac[i - 1], i);
	Inv[max(N, M)] = inverse(Fac[max(N, M)]);
	for (int i = max(N, M) - 1;i >= 0;--i)
		Inv[i] = Mult(Inv[i + 1], i + 1);
	for (int d = 1;d <= K;++d)
	{
		power[d][0] = 1;
		for (int i = 1;i <= N * M;++i)
			power[d][i] = Mult(power[d][i - 1], d);
	} 
	F[0][0] = 1;
	for (int d = 1;d <= K;++d)
	{
		for (int n = 0;n <= N;++n)
			for (int m = 0;m <= M;++m)
				G[0][n][m] = F[n][m];
		memset(G[1], 0, sizeof(G[1]));
		for (int m = 0;m <= M;++m)
			for (int x = 0, xs;x <= N;++x)
			{
				xs = Mult(Mult(power[d][x * (M - m)], power[K - d + 1][x * m]), Inv[x]);
				for (int n = 0;n <= N;++n)
					upd(G[1][n + x][m], Mult(G[0][n][m], xs));
			}
		memset(G[0], 0, sizeof(G[0]));
		for (int n = 0;n <= N;++n)
			for (int y = 0, xs;y <= M;++y)
			{
				xs = Mult(Mult(power[d][y * (N - n)], power[K - d + 1][y * n]), Inv[y]);
				for (int m = 0;m + y <= M;++m)
					upd(G[0][n][m + y], Mult(G[1][n][m], xs));
			}
		if (d == K)
			goto loop;
		memset(G[1], 0, sizeof(G[1]));
		for (int m = 0;m <= M;++m)
			for (int x = 0, xs;x <= N;++x)
			{
				xs = Mult(Mult(power[d][x * (M - m)], power[K - d][x * m]), Inv[x]);
				if (x & 1)
					xs = Sub(0, xs);
				for (int n = 0;n + x <= N;++n)
					upd(G[1][n + x][m], Mult(G[0][n][m], xs));
			}
		memset(G[0], 0, sizeof(G[0]));
		for (int n = 0;n <= N;++n)
			for (int y = 0, xs;y <= M;++y)
			{
				xs = Mult(Mult(power[d][y * (N - n)], power[K - d][y * n]), Inv[y]);
				if (y & 1)
					xs = Sub(0, xs);
				for (int m = 0;m + y <= M;++m)
					upd(G[0][n][m + y], Mult(G[1][n][m], xs));
			} 
		loop :
		for (int n = 0;n <= N;++n)
			for (int m = 0;m <= M;++m)
				F[n][m] = G[0][n][m];
	}
	printf("%d", Mult(F[N][M], Mult(Fac[N], Fac[M])));
	return 0;
}