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;
const int Maxn=105;
int f[Maxn][Maxn][Maxn],g[Maxn][Maxn][Maxn],C[Maxn][Maxn];
int main(){
    int n,m,c,mod;cin>>n>>m>>c>>mod;
    for(int i=0;i<105;C[i++][0]=1)
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    f[0][0][0]=1;
    auto ksm=[&](int x,int k){
        int ret=1,tmp=x;
        while(k){
            if(k&1)ret=1ll*ret*tmp%mod;
            tmp=1ll*tmp*tmp%mod;k>>=1;
        }
        return ret;
    };
    for(int k=1;k<=c;k++){
        static int base[Maxn*Maxn];
        for(int i=0,w=1;i<=n*m;i++,w=1ll*w*(c-k+1)%mod)base[i]=w;
        for(int j=0;j<=m;j++){
            int coef=ksm(k,m-j)-ksm(k-1,m-j);
            for(int i=0;i<=n;i++){
                int v=f[i][j][k-1];
                if(!v)continue;
                for(int d=0,w=1;i+d<=n;d++,w=1ll*w*coef%mod){
                    int V=v;
                    V=1ll*V*C[n-i][d]%mod;
                    V=1ll*V*base[d*j]%mod;
                    V=1ll*V*w%mod;
                    g[i+d][j][k]=(g[i+d][j][k]+V)%mod;
                }
            }
        }
        for(int i=0,w=1;i<=n*m;i++,w=1ll*w*k%mod)base[i]=w;
        for(int i=0;i<=n;i++){
            int coef=ksm(c-k+1,i)-ksm(c-k,i);
            for(int j=0;j<=m;j++){
                int v=g[i][j][k];
                if(!v)continue;
                for(int d=0,w=1;j+d<=m;d++,w=1ll*w*coef%mod){
                    int V=v;
                    V=1ll*V*C[m-j][d]%mod;
                    V=1ll*V*base[(n-i)*d]%mod;
                    V=1ll*V*w%mod;
                    f[i][j+d][k]=(f[i][j+d][k]+V)%mod;
                }
            }
        }
    }
    cout<<(f[n][m][c]+mod)%mod<<"\n";
    return 0;
}