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>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=105;
int mod;
int Pow(int x,int y) {
    int res=1;
    while(y) {
        if(y&1) res=res*(ll)x%mod;
        x=x*(ll)x%mod,y>>=1;
    }
    return res;
}
inline void Add(int &x,int y) { x+=y; if(x>=mod) x-=mod; }
int f[N][N][2],g[N][N][2],pw[N][N*N],C[N][N];
int coe[N][N][N][2];
int n,m,L;
void getC(int n) { for(int i=0;i<=n;++i) for(int j=0;j<=i;++j) C[i][j]=j?(C[i-1][j]+C[i-1][j-1])%mod:1; }
int main() {
    rd(n),rd(m),rd(L),rd(mod);
    for(int i=0;i<=L;++i) { pw[i][0]=1; for(int j=1;j<=n*m;++j) pw[i][j]=pw[i][j-1]*(ll)i%mod; }
    for(int k=1;k<=L;++k) {
        for(int j=0;j<=m;++j)
            for(int x=0;x<=n;++x)
                coe[k][j][x][0]=Pow(pw[L-k+1][j]*(ll)(pw[k][m-j]-pw[k-1][m-j]+mod)%mod,x);
        for(int i=0;i<=n;++i)
            for(int y=0;y<=m;++y)
                coe[k][i][y][1]=Pow(pw[k][n-i]%mod*(ll)(pw[L-k+1][i]-pw[L-k][i]+mod)%mod,y);
    }

    getC(max(n,m));
    f[0][0][0]=1;
    for(int k=1;k<=L;++k) {
        for(int d=0;d<2;++d) {
            for(int i=0;i<=n;++i)
                for(int j=0;j<=m;++j) if(f[i][j][d]) {
                    if(d==0) {
                        for(int x=0;i+x<=n;++x)
                            Add(g[i+x][j][1],f[i][j][0]*(ll)C[n-i][x]%mod*coe[k][j][x][0]%mod);
                    }
                    else {
                        Add(g[i][j][0],f[i][j][1]);
                        for(int y=1;j+y<=m;++y)
                            Add(g[i][j+y][0],f[i][j][1]*(ll)C[m-j][y]%mod*coe[k][i][y][1]%mod);
                    }
                }
            memcpy(f,g,sizeof(g));
            memset(g,0,sizeof(g));
        }
        // for(int d=0;d<2;++d,puts("")) for(int i=0;i<=n;++i,puts("")) for(int j=0;j<=m;++j) printf("%d ",f[i][j][d]);
        // puts("");
    }
    printf("%d",f[n][m][0]);
    return 0;
}