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>
#define N 101
#define ll long long
int a[N][N],b[N][N],c[N*N],d[N*N],e[N],f[N][N],g[N][N],i,j,k,l,m,n,o,p,s,t;
int main()
{
    scanf("%d%d%d%d",&m,&n,&o,&p);
    for(*e=e[1]=f[0][0]=1,i=2;i<=m||i<=n;i++)e[i]=(ll)(p-p/i)*e[p%i]%p;
    for(i=2;i<=m||i<=n;i++)e[i]=(ll)e[i]*e[i-1]%p;
    for(*c=*d=i=1;i<=o;i++)
    {
        for(j=0,s=t=1;j<=n;j++,s=(ll)s*i%p,t=t*(i-1ll)%p)for(*a[j]=k=1;k<=m;k++)a[j][k]=(ll)a[j][k-1]*(p+s-t)%p;
        for(j=0,s=t=1;j<=m;j++,s=s*(o-i+1ll)%p,t=(ll)t*(o-i)%p)for(*b[j]=k=1;k<=n;k++)b[j][k]=(ll)b[j][k-1]*(p+s-t)%p;
        for(j=1,s=m*n;j<=s;j++)c[j]=(ll)c[j-1]*i%p;
        for(j=1;j<=s;j++)d[j]=d[j-1]*(o-i+1ll)%p;
        for(j=0;j<=m;j++)for(k=0;k<=n;f[j][k++]=0)for(l=0;j+l<=m;l++)g[j+l][k]=(g[j+l][k]+(ll)f[j][k]*e[l]%p*a[n-k][l]%p*d[k*l])%p;
        for(j=0;j<=m;j++)for(k=0;k<=n;g[j][k++]=0)for(l=0;k+l<=n;l++)f[j][k+l]=(f[j][k+l]+(ll)g[j][k]*e[l]%p*b[j][l]%p*c[(m-j)*l])%p;
    }
    for(s=f[m][n],i=1;i<=m;i++)s=(ll)s*i%p;
    for(i=1;i<=n;i++)s=(ll)s*i%p;
    return 0*printf("%d\n",s);
}