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>

using namespace std;

#define ll long long
#define mul(a, b) (F.reduce((ll)(a) * (ll)(b)))

int n, m, K, MOD;

int f[105][105][4];
int pwr[105][10005];
int C[105][105];

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod F(2);

int fpow(int base, int exponent)
{
    int ans = 1;
    int cur = base;
    while (exponent) {
        if (exponent & 1) ans = mul(ans, cur);
        cur = mul(cur, cur); exponent >>= 1;
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &K, &MOD);
    F = FastMod(MOD);
    C[0][0] = 1;
    for (int i = 1; i <= 102; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            if (C[i][j] >= MOD) C[i][j] -= MOD;
        }
    }
    for (int i = 0; i <= 100; i++) {
        pwr[i][0] = 1;
        for (int j = 1; j <= 10000; j++) {
            pwr[i][j] = mul(pwr[i][j-1], i);
        }
    }
    f[0][0][0] = 1;
    for (int i = 0; i < K; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                //if (f[j][k][0]) printf("0 %d %d %d\n", i, j, k);
                for (int l = 0; j + l <= n; l++) {
                    f[j+l][k][1] += mul(pwr[i+1][l * (m - k)], mul(C[n-j][l],
                        mul(pwr[K - i][l * k], f[j][k][0])));
                    if (f[j+l][k][1] >= MOD) f[j+l][k][1] -= MOD;
                }
            }
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                f[j][k][0] = 0;
            }
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                //if (f[j][k][1]) printf("1 %d %d %d\n", i, j, k);
                for (int l = 0; k + l <= m; l++) {
                    f[j][k+l][2] += mul(pwr[i+1][l * (n - j)], mul(C[m-k][l],
                        mul(pwr[K - i][l * j], f[j][k][1])));
                    if (f[j][k+l][2] >= MOD) f[j][k+l][2] -= MOD;
                }
            }
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                //if (f[j][k][2]) printf("2 %d %d %d\n", i, j, k);
                int n1pwr = 1;
                for (int l = 0; j + l <= n; l++) {
                    //int oldv = f[j+l][k][3];
                    if (n1pwr == 1) {
                        f[j+l][k][3] += mul(pwr[i+1][l * (m - k)], mul(C[n-j][l],
                            mul(pwr[K - i - 1][l * k], f[j][k][2])));
                        if (f[j+l][k][3] >= MOD) f[j+l][k][3] -= MOD;
                    } else {
                        f[j+l][k][3] -= mul(pwr[i+1][l * (m - k)], mul(C[n-j][l],
                            mul(pwr[K - i - 1][l * k], f[j][k][2])));
                        if (f[j+l][k][3] < 0) f[j+l][k][3] += MOD;
                    }
                    //if (oldv || f[j+l][k][3]) printf("modify %d %d %d->%d\n", j+l, k, oldv, f[j+l][k][3]);
                    n1pwr = -n1pwr;
                }
            }
        }
        /*for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                printf("f[%d][%d][%d] = %d", j, k, 3, f[j][k][3]);
            }
        }*/
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                //if (f[j][k][3]) printf("3 %d %d %d\n", i, j, k);
                int n1pwr = 1;
                for (int l = 0; k + l <= m; l++) {
                    if (n1pwr == 1) {
                        f[j][k+l][0] += mul(pwr[i+1][l * (n - j)], mul(C[m-k][l],
                            mul(pwr[K - i - 1][l * j], f[j][k][3])));
                        if (f[j][k+l][0] >= MOD) f[j][k+l][0] -= MOD;
                    } else {
                        f[j][k+l][0] -= mul(pwr[i+1][l * (n - j)], mul(C[m-k][l],
                            mul(pwr[K - i - 1][l * j], f[j][k][3])));
                        if (f[j][k+l][0] < 0) f[j][k+l][0] += MOD;
                    }
                    n1pwr = -n1pwr;
                }
            }
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                f[j][k][1] = f[j][k][2] = f[j][k][3] = 0;
            }
        }
    }
    printf("%d", f[n][m][0]);
    return 0;
}