#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using vi = vector<long long>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<pair<long long, long long> >;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
const long long inf = 1001001001001001001;
const long long INF = 1001001001;
long long mod;
const double eps = 1e-10;
template <class T>
bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
void out(T a) {
  cout << a << '\n';
}
template <class T>
void outp(T a) {
  cout << '(' << a.first << ',' << a.second << ')' << '\n';
}
template <class T>
void outvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++)
    cout << '(' << v[i].first << ',' << v[i].second << ')';
  cout << '\n';
}
template <class T>
void outvvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outvp(v[i]);
}
template <class T>
void outv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) {
    if (i) cout << ' ';
    cout << v[i];
  }
  cout << '\n';
}
template <class T>
void outvv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outv(v[i]);
}
template <class T>
bool isin(T x, T l, T r) {
  return (l) <= (x) && (x) <= (r);
}
template <class T>
void yesno(T b) {
  if (b)
    out("yes");
  else
    out("no");
}
template <class T>
void YesNo(T b) {
  if (b)
    out("Yes");
  else
    out("No");
}
template <class T>
void YESNO(T b) {
  if (b)
    out("YES");
  else
    out("NO");
}
template <class T>
void outset(T s) {
  auto itr = s.begin();
  while (itr != s.end()) {
    if (itr != s.begin()) cout << ' ';
    cout << *itr;
    itr++;
  }
  cout << '\n';
}
void outs(long long a, long long b) {
  if (a >= inf - 100)
    out(b);
  else
    out(a);
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long modpow(long long a, long long b) {
  long long res = 1;
  a %= mod;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, m, K;
  cin >> n >> m >> K >> mod;
  if (K >= 90) {
    out(0);
    return 0;
  };
  vvvi dp(n + 1, vvi(m + 1, vi(K + 1)));
  vvi modcom(n + 3, vi(n + 3));
  modcom[0][0] = 1;
  for (long long i = 0; i < (long long)(n + 2); i++)
    for (long long j = 0; j < (long long)(n + 2); j++) {
      modcom[i][j] %= mod;
      modcom[i + 1][j] += modcom[i][j];
      modcom[i + 1][j + 1] += modcom[i][j];
    }
  vi fac(n + 3);
  fac[0] = 1;
  for (long long i = 0; i < (long long)(n + 2); i++)
    fac[i + 1] = fac[i] * (i + 1) % mod;
  for (long long i = 0; i < (long long)(n + 1); i++) {
    for (int j = m; j >= 0; j--) {
      for (long long k = 0; k < (long long)(K + 1); k++) {
        if (i < k) continue;
        if (i == 0) {
          dp[i][j][k]++;
          continue;
        }
        if (j == m) {
          dp[i][j][k] = fac[i];
          continue;
        }
        if (j == m - 1) {
          if (k == 1) dp[i][j][k] = fac[i];
          continue;
        }
        for (long long t = 0; t < (long long)(i); t++)
          for (long long u = max(0ll, k + t - i - 1);
               u < (long long)(min(k + 1, t + 1)); u++)
            if (dp[t][j + 1][u] && dp[i - 1 - t][j + 1][k - u])
              dp[i][j][k] += dp[t][j + 1][u] * dp[i - 1 - t][j + 1][k - u] %
                             mod * modcom[i - 1][t] % mod;
        dp[i][j][k] %= mod;
      }
    }
  }
  out(dp[n][0][K]);
}

### Prompt

Develop a solution in CPP to the problem described below:

Let c_1, c_2, …, c_n be a permutation of integers 1, 2, …, n. Consider all subsegments of this permutation containing an integer x. Given an integer m, we call the integer x good if there are exactly m different values of maximum on these subsegments.

Cirno is studying mathematics, and the teacher asks her to count the number of permutations of length n with exactly k good numbers.

Unfortunately, Cirno isn't good at mathematics, and she can't answer this question. Therefore, she asks you for help.

Since the answer may be very big, you only need to tell her the number of permutations modulo p.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

A sequence a is a subsegment of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains four integers n, m, k, p (1 ≤ n ≤ 100, 1 ≤ m ≤ n, 1 ≤ k ≤ n, 1 ≤ p ≤ 10^9).

Output

Output the number of permutations modulo p.

Examples

Input


4 3 2 10007


Output


4


Input


6 4 1 769626776


Output


472


Input


66 11 9 786747482


Output


206331312


Input


99 30 18 650457567


Output


77365367

Note

In the first test case, there are four permutations: [1, 3, 2, 4], [2, 3, 1, 4], [4, 1, 3, 2] and [4, 2, 3, 1].

Take permutation [1, 3, 2, 4] as an example:

For number 1, all subsegments containing it are: [1], [1, 3], [1, 3, 2] and [1, 3, 2, 4], and there're three different maxima 1, 3 and 4.

Similarly, for number 3, there're two different maxima 3 and 4. For number 2, there're three different maxima 2, 3 and 4. And for number 4, there're only one, that is 4 itself.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using vi = vector<long long>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<pair<long long, long long> >;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
const long long inf = 1001001001001001001;
const long long INF = 1001001001;
long long mod;
const double eps = 1e-10;
template <class T>
bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
void out(T a) {
  cout << a << '\n';
}
template <class T>
void outp(T a) {
  cout << '(' << a.first << ',' << a.second << ')' << '\n';
}
template <class T>
void outvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++)
    cout << '(' << v[i].first << ',' << v[i].second << ')';
  cout << '\n';
}
template <class T>
void outvvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outvp(v[i]);
}
template <class T>
void outv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) {
    if (i) cout << ' ';
    cout << v[i];
  }
  cout << '\n';
}
template <class T>
void outvv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outv(v[i]);
}
template <class T>
bool isin(T x, T l, T r) {
  return (l) <= (x) && (x) <= (r);
}
template <class T>
void yesno(T b) {
  if (b)
    out("yes");
  else
    out("no");
}
template <class T>
void YesNo(T b) {
  if (b)
    out("Yes");
  else
    out("No");
}
template <class T>
void YESNO(T b) {
  if (b)
    out("YES");
  else
    out("NO");
}
template <class T>
void outset(T s) {
  auto itr = s.begin();
  while (itr != s.end()) {
    if (itr != s.begin()) cout << ' ';
    cout << *itr;
    itr++;
  }
  cout << '\n';
}
void outs(long long a, long long b) {
  if (a >= inf - 100)
    out(b);
  else
    out(a);
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long modpow(long long a, long long b) {
  long long res = 1;
  a %= mod;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, m, K;
  cin >> n >> m >> K >> mod;
  if (K >= 90) {
    out(0);
    return 0;
  };
  vvvi dp(n + 1, vvi(m + 1, vi(K + 1)));
  vvi modcom(n + 3, vi(n + 3));
  modcom[0][0] = 1;
  for (long long i = 0; i < (long long)(n + 2); i++)
    for (long long j = 0; j < (long long)(n + 2); j++) {
      modcom[i][j] %= mod;
      modcom[i + 1][j] += modcom[i][j];
      modcom[i + 1][j + 1] += modcom[i][j];
    }
  vi fac(n + 3);
  fac[0] = 1;
  for (long long i = 0; i < (long long)(n + 2); i++)
    fac[i + 1] = fac[i] * (i + 1) % mod;
  for (long long i = 0; i < (long long)(n + 1); i++) {
    for (int j = m; j >= 0; j--) {
      for (long long k = 0; k < (long long)(K + 1); k++) {
        if (i < k) continue;
        if (i == 0) {
          dp[i][j][k]++;
          continue;
        }
        if (j == m) {
          dp[i][j][k] = fac[i];
          continue;
        }
        if (j == m - 1) {
          if (k == 1) dp[i][j][k] = fac[i];
          continue;
        }
        for (long long t = 0; t < (long long)(i); t++)
          for (long long u = max(0ll, k + t - i - 1);
               u < (long long)(min(k + 1, t + 1)); u++)
            if (dp[t][j + 1][u] && dp[i - 1 - t][j + 1][k - u])
              dp[i][j][k] += dp[t][j + 1][u] * dp[i - 1 - t][j + 1][k - u] %
                             mod * modcom[i - 1][t] % mod;
        dp[i][j][k] %= mod;
      }
    }
  }
  out(dp[n][0][K]);
}

```