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 N = 110;

int n, m, d, Mod;
int f[N][N][N], g[N][N][N];
int cf[N][N][N], cg[N][N][N];
int C[N][N];

int add(int a, int b) {
  return (a += b) >= Mod ? a - Mod : a;
}

int sub(int a, int b) {
  return (a -= b) < 0 ? a + Mod : a;
}

int mul(int a, int b) {
  return 1ll * a * b % Mod;
}

int fast_pow(int a, int b) {
  int res = 1;
  for (; b; b >>= 1, a = mul(a, a)) {
    if (b & 1) res = mul(res, a);
  }
  return res;
}

void upd(int &a, int b) {
  a = add(a, b);
}

void init() {
  for (int i = 0; i <= 100; i++) C[i][0] = 1;
  for (int i = 1; i <= 100; i++) {
    for (int j = 1; j <= i; j++) {
      C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
  }
  for (int k = 1; k <= d; k++) {
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        int tmp = sub(fast_pow(k, m - i), fast_pow(k - 1, m - i));
        cf[k][i][j] = fast_pow(mul(tmp, fast_pow(d - k + 1, i)), j);
      }
    }
  }
  for (int k = 1; k <= d; k++) {
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        int tmp = sub(fast_pow(d - k + 1, i), fast_pow(d - k, i));
        cg[k][i][j] = fast_pow(mul(tmp, fast_pow(k, n - i)), j);
      }
    }
  }
}

int main() {
  cin >> n >> m >> d >> Mod;
  init();
  f[1][0][0] = 1;
  for (int k = 1; k <= d; k++) {
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        int tmp = f[k][i][j];
        for (int p = 0; i + p <= n; p++) {
          upd(g[k][i + p][j], mul(tmp, mul(C[n - i][p], cf[k][j][p])));
        }
        tmp = g[k][i][j];
        for (int p = 0; j + p <= m; p++) {
          upd(f[k + 1][i][j + p], mul(tmp, mul(C[m - j][p], cg[k][i][p])));
        }
      }
    }
  }
  cout << f[d + 1][n][m] << endl;
  return 0;
}