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;
typedef long long i64;
const int N = 1e2+5; int P;
int n, m, K, f[N][N], g[N][N], pw[N][N], coe[N][N][N][2], C[N][N]; void fix(int &x) { x<P?0:x-=P; }
int main()
{
    scanf("%d%d%d%d", &n, &m, &K, &P); if(n < m) swap(n, m); f[0][0] = 1;
    for(int i = 0, j; i <= n; ++i) for(C[i][0] = 1, j = 1; j <= i; fix(C[i][j]=C[i-1][j-1]+C[i-1][j]), ++j);
    for(int i = 0, j; i <= K; ++i) for(pw[i][0] = 1, j = 1; j <= n; pw[i][j] = (i64)pw[i][j-1]*i%P, ++j);
    for(int v = 1; v <= K; ++v) for(int i = 0, j; i <= m; ++i) for(coe[v][i][0][0] = 1, j = 1; j <= n; ++j) 
        coe[v][i][j][0] = (i64)coe[v][i][j-1][0]*pw[K-v+1][i]%P*(pw[v][m-i]+P-pw[v-1][m-i])%P;
    for(int v = 1; v <= K; ++v) for(int i = 0, j; i <= n; ++i) for(coe[v][i][0][1] = 1, j = 1; j <= m; ++j) 
        coe[v][i][j][1] = (i64)coe[v][i][j-1][1]*pw[v][n-i]%P*(pw[K-v+1][i]+P-pw[K-v][i])%P;
    for(int v = 1; v <= K; ++v) 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])
            if(!d) for(int k = 0; i+k <= n; ++k) fix(g[i+k][j]+=(i64)coe[v][j][k][0]*f[i][j]%P*C[n-i][k]%P);
            else for(int k = 0; j+k <= m; ++k) fix(g[i][j+k]+=(i64)coe[v][i][k][1]*f[i][j]%P*C[m-j][k]%P);
        memcpy(f, g, sizeof(f)), memset(g, 0, sizeof(g));
    }  
    printf("%d\n", f[n][m]);
    return 0;
}