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;
#define ll long long
const int N=105;
ll d[N][N],f[N][N],e[N][N],ifa[N];
ll expo(ll a,int b,ll p){
    ll c=1ll;
    while(b){
        if(b&1)c=c*a%p;
        b>>=1; a=a*a%p;
    }
    return c;
}
int main(){
    ll w=1ll,ww,p;
    int n,m,q,K,k,t,i,j,h;
    scanf("%d%d%d%lld",&n,&m,&q,&p);t=n<m?m:n;
    for(i=1;i<=t;++i)w=w*i%p;
    ifa[t]=w=expo(w,p-2ll,p);
    for(i=t;i;--i)ifa[i-1]=w=w*i%p;
    for(i=1;i<=q;++i){
        e[i][0]=w=1ll;
        for(j=1;j<=t;++j)e[i][j]=w=w*i%p;
    }
    for(i=1;i<=q;++i){
        for(j=1;j<=t;++j)if((f[i][j]=e[i][j]-e[i-1][j])<0ll)f[i][j]+=p;
    }
    d[0][0]=1ll;
    for(k=1,K=q;K;++k,--K){
        for(j=0;j<=m;++j){
            w=e[K][j]*f[k][m-j]%p;
//          printf("j=%d w=%lld\n",j,w);
            for(i=n-1;~i;--i){
                ww=d[i][j];
                for(h=i+1;h<=n;++h){
                    ww=ww*w%p;
                    d[h][j]=(d[h][j]+ww*ifa[h-i])%p;
                }
            }
        }
        /*
        printf("\nk=%d K=%d\n",k,K);
        for(i=0;i<=n;++i){
            for(j=0;j<=m;++j){
                printf("%d ",d[i][j]);
            }
            printf("\n");
        }*/
        for(i=0;i<=n;++i){
            w=f[K][i]*e[k][n-i]%p;
            for(j=m-1;~j;--j){
                ww=d[i][j];
                for(h=j+1;h<=m;++h){
                    ww=ww*w%p;
                    d[i][h]=(d[i][h]+ww*ifa[h-j])%p;
                }
            }
        }
        /*
        printf("\nk=%d K=%d\n",k,K);
        for(i=0;i<=n;++i){
            for(j=0;j<=m;++j){
                printf("%d ",d[i][j]);
            }
            printf("\n");
        }*/
    }
    w=d[n][m];
    for(i=1;i<=n;++i)w=w*i%p;
    for(i=1;i<=m;++i)w=w*i%p;
    printf("%lld",w);
    return 0;
}