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>

const int N = 110;

int dp[N][N][N][2];
int moder;
int comb[N][N], power[N][N];

void addmult(int &a, int b, int c){a = (a + 1ll * b * c) % moder;}

int main(){
    int n, m, k;
    scanf("%d%d%d%d", &n, &m, &k, &moder);
    for (int i = 0; i < N; ++ i){
        comb[i][0] = 1;
        for (int j = 1; j <= i; ++ j){
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % moder;
        }
        power[i][0] = 1;
        for (int j = 1; j < N; ++ j){
            power[i][j] = 1ll * power[i][j - 1] * i % moder;
        }
    }
    dp[1][0][0][0] = 1;
    for (int i = 1; i <= k; ++ i){
        for (int j = 0; j <= n; ++ j){
            for (int K = 0; K <= m; ++ K){
                int now = dp[i][j][K][0], coe1 = power[k - i + 1][j], coe2 = power[i][n - j] - power[i - 1][n - j];
                coe2 += coe2 < 0 ? moder : 0;
                int coe = 1ll * coe1 * coe2 % moder;
                for (int u = 0; K + u <= m; ++ u){
                    addmult(dp[i][j][K + u][1], now, comb[m - K][u]);
                    now = 1ll * coe * now % moder;
                }
            }
        }
        for (int j = 0; j <= n; ++ j){
            for (int K = 0; K <= m; ++ K){
                int now = dp[i][j][K][1], coe1 = power[k - i + 1][K] - power[k - i][K], coe2 = power[i][m - K];
                coe1 += coe1 < 0 ? moder : 0;
                int coe = 1ll * coe1 * coe2 % moder;
                for (int u = 0; j + u <= n; ++ u){
                    addmult(dp[i + 1][j + u][K][0], now, comb[n - j][u]);
                    now = 1ll * coe * now % moder;
                }
            }
        }
    }
    printf("%d\n", dp[k + 1][n][m][0]);
    return 0;
}