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;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 103;

int mo;

template<typename T1,typename T2> inline T1 ad(T1 &a,T2 b){return a=a+b>=mo?a+b-mo:a+b;}
template<typename T1,typename T2> inline T1 dl(T1 &a,T2 b){return a=a>=b?a-b:a-b+mo;}


inline lint powa(lint a,lint t)
{
	lint b=1;
	while(t){if(t&1)b=b*a%mo;a=a*a%mo,t>>=1;}
	return b;
}

inline lint inva(lint a)
{
	return powa(a,mo-2);
}

lint C[_][_]={0};

inline void fuck(int n=_-1)
{
	for(int i=0;i<=n;i++)C[i][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}

int n,m,lim;
lint f[_][_][_][2]={0},tran[_][_][_][2]={0};

int main()
{
	n=ty(),m=ty(),lim=ty(),mo=ty();

	fuck();
	for(int i=0;i<lim;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=m;k++)
			{
				tran[i][j][k][0]=(powa(i+1,n-j)-powa(i,n-j)+mo)%mo*powa(lim-i,j)%mo;
				tran[i][j][k][1]=(powa(lim-i,k)-powa(lim-i-1,k)+mo)%mo*powa(i+1,m-k)%mo;
			}

	f[0][0][0][0]=1;
	for(int i=0;i<lim;i++)
	{
		for(int j=0;j<=n;j++)
			for(int k=0;k<=m;k++)
				if(f[i][j][k][0])
					for(int a=0,x=1;a+k<=m;a++,x=1ll*x*tran[i][j][k][0]%mo)
						ad(f[i][j][k+a][1],f[i][j][k][0]*x%mo*C[m-k][a]%mo);
		for(int j=0;j<=n;j++)
			for(int k=0;k<=m;k++)
				if(f[i][j][k][1])
					for(int a=0,x=1;a+j<=n;a++,x=1ll*x*tran[i][j][k][1]%mo)
						ad(f[i+1][j+a][k][0],f[i][j][k][1]*x%mo*C[n-j][a]%mo);
	}

	printf("%lld\n",f[lim][n][m][0]);

	return 0;
}