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:
#pragma GCC optimize(2,3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
	in int read()
	{
		int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;
		x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;
	}
	in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
	in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
	in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
	in void flush() {if(C>1<<22) ot();}
	template <typename T>
	in void write(T x,char t)
	{
		int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
		if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
	}
	in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=1e2+5;
int q,n,m,k,p,c[N][N],pw[N][N],f[2][N][N];
in void M(int &x) {x-=p;x+=x>>31&p;}
in void cl(int x) {for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)f[x][i][j]=0;}
int main()
{
	n=read(),m=read(),k=read(),p=read();for(int i=0;i<=max(n,m);i++) c[i][0]=1;
	for(int i=1;i<=max(n,m);i++) for(int j=1;j<=i;j++) M(c[i][j]=c[i-1][j-1]+c[i-1][j]);
	for(int i=0;i<=k;i++) pw[i][0]=1;
	for(int i=0;i<=k;i++) for(int j=1;j<=max(n,m);j++) pw[i][j]=1ll*pw[i][j-1]*i%p;
	f[0][0][0]=1;
	for(int t=1;t<=k;t++)
	{
		cl(q^1);
		for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) if(f[q][i][j])
		{
			int x=f[q][i][j],y=1ll*pw[k-t+1][j]*pw[t][m-j]%p;
			for(int a=0;a<=n-i;a++,x=1ll*x*y%p) M(f[q^1][i+a][j]+=1ll*c[n-i][a]*x%p);
		}q^=1;cl(q^1);
		for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) if(f[q][i][j])
		{
			int x=f[q][i][j],y=1ll*pw[k-t+1][i]*pw[t][n-i]%p;
			for(int b=0;b<=m-j;b++,x=1ll*x*y%p) M(f[q^1][i][j+b]+=1ll*c[m-j][b]*x%p);
		}q^=1;cl(q^1);
		for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) if(f[q][i][j])
		{
			int x=f[q][i][j],y=1ll*(p-pw[k-t][j])*pw[t][m-j]%p;
			for(int a=0;a<=n-i;a++,x=1ll*x*y%p) M(f[q^1][i+a][j]+=1ll*c[n-i][a]*x%p);
		}q^=1;cl(q^1);
		for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) if(f[q][i][j])
		{
			int x=f[q][i][j],y=1ll*(p-pw[k-t][i])*pw[t][n-i]%p;
			for(int b=0;b<=m-j;b++,x=1ll*x*y%p) M(f[q^1][i][j+b]+=1ll*c[m-j][b]*x%p);
		}q^=1;
	}
	write(f[q][n][m],'\n');
	return ot(),0;
}
//Author: disangan233