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>
#define maxn 205
#define ll long long
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
int mod;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef __int128_t i128;
typedef __uint128_t u128;

struct Mod32 {
	Mod32():n_(0) {}
	Mod32(u32 n):n_(init(n)) {}
	static u32 init(u32 w) { return reduce(u64(w) * r2); }
	static void set_mod(u32 m) {
		mod=m; assert(mod&1);
		inv=m; rep(i,0,4) inv*=2-inv*m;
		r2=-u64(m)%m;
	}
	static u32 reduce(u64 x) {
		u32 y=u32(x>>32)-u32((u64(u32(x)*inv)*mod)>>32);
		return i32(y)<0?y+mod:y;
	}
	Mod32& operator += (Mod32 rhs) { n_+=rhs.n_-mod; if (i32(n_)<0) n_+=mod; return *this; }
	Mod32 operator + (Mod32 rhs) const { return Mod32(*this)+=rhs; }
	Mod32& operator -= (Mod32 rhs) { n_-=rhs.n_; if (i32(n_)<0) n_+=mod; return *this; }
	Mod32 operator - (Mod32 rhs) const { return Mod32(*this)-=rhs; }
	Mod32& operator *= (Mod32 rhs) { n_=reduce(u64(n_)*rhs.n_); return *this; }
	Mod32 operator * (Mod32 rhs) const { return Mod32(*this)*=rhs; }
	u32 get() const { return reduce(n_); }
	static u32 mod,inv,r2;
	u32 n_;
};
u32 Mod32::mod,Mod32::inv,Mod32::r2;
Mod32 one,zero;
int n, m, c;
Mod32 nr[maxn][maxn], u[maxn][maxn];
Mod32 dp[maxn][maxn];
Mod32 pw[maxn][maxn];
Mod32 jc[maxn], bjc[maxn];
void calnx(int a, int b, int tp) {
	// a : 余下 b : 这些 
	for (int s = 0; s <= n + m; s++) {
		for (int i = 0; i <= n; i++)
			for (int j = max(0, s - i); j <= m; j++) {
				u[i][j] = 0;
				if (i + j == s) u[i][j] = dp[i][j];
			}
		for (int i = 0; i <= n; i++)
			for (int j = max(0, s - i); j <= m; j++) {
				if (i) 
					u[i][j] += u[i - 1][j] * pw[a][m - j] * pw[b][j];
				if (j)
					u[i][j] += u[i][j - 1] * pw[a][n - i] * pw[b][i];
			}
		for (int i = 0; i <= n; i++)
			for (int j = max(0, s - i); j <= m; j++) {
				Mod32 kk = u[i][j] * bjc[i + j - s];
				if (tp && (i + j - s) % 2 == 1) nr[i][j] -= kk;
				else nr[i][j] += kk;
				u[i][j] = 0;
			}
	}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			dp[i][j] = nr[i][j], 
			nr[i][j] = 0;
}
Mod32 ksm(Mod32 a, ll b) {
	if (!b) return one;
	Mod32 ns = ksm(a, b >> 1);
	ns = ns * ns;
	if (b & 1) ns *= a;
	return ns;
}
int main()
{
	cin >> n >> m >> c >> mod;
	Mod32::set_mod(mod); one=Mod32(1); zero=Mod32(0);
	jc[0] = bjc[0] = one;
	for (int i = 1; i < maxn; i++)
		jc[i] = jc[i - 1] * i, 
		bjc[i] = ksm(jc[i], mod - 2);
	for (int i = 0; i < maxn; i++) {
		pw[i][0] = 1;
		for (int j = 1; j < maxn; j++)
			pw[i][j] = pw[i][j - 1] * i;
	}
	for (int i = 0; i <= 2 * c + 1; i++) {
		int nr = (i + 1) / 2;
		if (i == 0) dp[0][0] = 1;
		else {
			if (i % 2 == 1) calnx(nr, c + 1 - nr, 0);
			else calnx(nr, c - nr, 1);
		}
	}
	dp[n][m] = dp[n][m] * jc[n] * jc[m];
	cout << dp[n][m].get() << endl; 
	return 0;
}
/*
100 100 100 998244353
*/