Problem: A tree is a connected graph without cycles.

Two trees, consisting of n vertices each, are called isomorphic if there exists a permutation p: {1, ..., n} → {1, ..., n} such that the edge (u, v) is present in the first tree if and only if the edge (pu, pv) is present in the second tree.

Vertex of the tree is called internal if its degree is greater than or equal to two.

Count the number of different non-isomorphic trees, consisting of n vertices, such that the degree of each internal vertex is exactly d. Print the answer over the given prime modulo mod.

Input

The single line of the input contains three integers n, d and mod (1 ≤ n ≤ 1000, 2 ≤ d ≤ 10, 108 ≤ mod ≤ 109) — the number of vertices in the tree, the degree of internal vertices and the prime modulo.

Output

Print the number of trees over the modulo mod.

Examples

Input

5 2 433416647


Output

1


Input

10 3 409693891


Output

2


Input

65 4 177545087


Output

910726

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int d;
int num_leaf(int sz) {
  if (sz == 1) {
    return 1;
  }
  if (sz == 2) {
    return 1;
  }
  sz--;
  int cnt = d;
  sz -= d;
  if (sz < 0) {
    return -1;
  }
  while (sz) {
    if (sz < d - 1) {
      return -1;
    }
    sz -= (d - 1);
    cnt += (d - 1);
    cnt--;
  }
  return cnt;
}
int lf[1002];
long long int dp[1002];
bool us[1002];
long long int tmp[1002][1002][11];
long long int tmp2[1002][1002][11];
long long int MOD;
bool us2[1002];
long long int dp2[1002];
long long int ppow(long long int i, long long int j) {
  long long int res = 1;
  while (j) {
    if (j & 1LL) {
      res *= i;
      if (res >= MOD) res %= MOD;
    }
    j >>= 1LL;
    i *= i;
    if (i >= MOD) i %= MOD;
  }
  return res;
}
long long int sel(long long int val, int ch) {
  val += ch - 1;
  long long int up = 1;
  long long int dw = 1;
  for (int j = 0; j < ch; j++) {
    up *= (val - j);
    if (up >= MOD) up %= MOD;
    dw *= (j + 1);
    if (dw >= MOD) dw %= MOD;
  }
  up *= ppow(dw, MOD - 2);
  if (up >= MOD) up %= MOD;
  return up;
}
long long int ww[1002][11];
inline long long int dfs2(int sz) {
  if (sz == 1) {
    return 1;
  }
  if (us2[sz]) return dp2[sz];
  us2[sz] = true;
  dp2[sz] = 0;
  tmp2[sz][0][0] = 1;
  int deg = d - 1;
  for (int add = 1; add <= sz - 1; add++) {
    if ((add - 1) % deg) {
      continue;
    }
    long long int way = dfs2(add);
    for (int z = 0; z <= deg; z++) {
      ww[sz][z] = sel(way, z);
    }
    for (int j = sz - 1 - add; j >= 0; j--) {
      for (int k = deg - 1; k >= 0; k--) {
        long long int bs = tmp2[sz][j][k];
        for (int z = k + 1; z <= deg; z++) {
          if ((z - k) * add + j > sz - 1) break;
          tmp2[sz][(z - k) * add + j][z] += bs * ww[sz][z - k];
          if (tmp2[sz][(z - k) * add + j][z] > MOD) {
            tmp2[sz][(z - k) * add + j][z] %= MOD;
          }
        }
      }
    }
  }
  dp2[sz] = tmp2[sz][sz - 1][deg];
  return dp2[sz];
}
inline long long int dfs(int sz) {
  if (sz <= 1) {
    return 1;
  }
  if (us[sz]) return dp[sz];
  us[sz] = true;
  int maxi = (sz - 1) / 2;
  tmp[sz][0][0] = 1;
  for (int add = 1; add <= maxi; add++) {
    if (add > 2 && ((add - 1) % (d - 1))) continue;
    for (int j = sz - 1 - add; j >= 0; j--) {
      for (int k = d - 1; k >= 0; k--) {
        long long int bs = tmp[sz][j][k];
        long long int way = dfs2(add);
        for (int z = k + 1; z <= d; z++) {
          if ((z - k) * add + j > sz - 1) break;
          tmp[sz][(z - k) * add + j][z] += bs * sel(way, z - k);
          if (tmp[sz][(z - k) * add + j][z] > MOD) {
            tmp[sz][(z - k) * add + j][z] %= MOD;
          }
        }
      }
    }
  }
  dp[sz] = tmp[sz][sz - 1][d];
  return dp[sz];
}
int main() {
  int n;
  cin >> n >> d >> MOD;
  for (int i = 0; i < 1002; i++) {
    lf[i] = num_leaf(i);
  }
  long long int ans = dfs(n);
  if (n % 2 == 0) {
    long long int ans2 = dfs2(n / 2);
    ans += sel(ans2, 2);
    if (ans >= MOD) ans %= MOD;
  }
  printf("%lld\n", ans);
  return 0;
}