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>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define inver(a) power(a,mod-2)
using namespace std;
inline char nc()
{
    return getchar();
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
    x=0; int f=1,ch=nc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
    while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
    x*=f;
}
typedef long long ll;
const int maxk=100+5;
const int maxn=100+5;
int mod;
int n,m,k;
int fac[maxn];
int inv[maxn];
int f[maxk][maxn][maxn][2];
inline int sub(int x) {return x<0?x+mod:x;}
inline void upd(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
ll power(ll x,ll y)
{
    ll re=1;
    while(y)
    {
        if(y&1) re=re*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return re;
}
void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%mod;
    inv[n]=inver(fac[n]);
    for(int i=n;i>=1;--i) inv[i-1]=(ll)inv[i]*i%mod;
}
int main()
{
    read(n),read(m),read(k),read(mod);
    f[1][0][0][0]=1;
    init(max(n,m));
    for(int t=1;t<=k;++t)
    {
        for(int i=0;i<=n;++i) 
        {
            int a=1,b=1,c=power(k-t+1,m);
            int w=inver(k-t+1);
            for(int j=m;j>=0;--j)
            {
                int r=(ll)sub(a-b)*c%mod;
                if(f[t][i][j][0]) 
                {
                    // debug("%d %d %d %d %d\n",t,i,j,0,f[t][i][j][0]);
                    upd(f[t][i][j][1],f[t][i][j][0]);
                    for(int x=1,coe=1;x+i<=n;++x)
                    {
                        coe=(ll)coe*r%mod;
                        upd(f[t][i+x][j][1],(ll)f[t][i][j][0]*coe%mod*inv[x]%mod);
                    }
                }
                a=(ll)a*t%mod;
                b=(ll)b*(t-1)%mod;
                c=(ll)c*w%mod;
            }
        }
        for(int j=0;j<=m;++j) 
        {
            int a=1,b=1,c=power(t,n);
            int w=inver(t);
            for(int i=0;i<=n;++i)
            {
                int r=(ll)sub(a-b)*c%mod;
                if(f[t][i][j][1]) 
                {
                    // debug("%d %d %d %d %d\n",t,i,j,1,f[t][i][j][1]);
                    upd(f[t+1][i][j][0],f[t][i][j][1]);
                    for(int x=1,coe=1;x+j<=m;++x)
                    {
                        coe=(ll)coe*r%mod;
                        upd(f[t+1][i][j+x][0],(ll)f[t][i][j][1]*coe%mod*inv[x]%mod);
                    }
                }
                a=(ll)a*(k-t+1)%mod;
                b=(ll)b*(k-t)%mod;
                c=(ll)c*w%mod;
            }
        }
    }
    printf("%lld\n",(ll)f[k+1][n][m][0]*fac[n]%mod*fac[m]%mod);
    return 0;
}