1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MAXN = 1015;
const int MAXK = 12;

int MOD;
LL SN[MAXN][MAXN];
// najw. po prawej, najw. po prawej a kolejny po lewej
LL DP1[MAXN][MAXK], DP2[MAXN][MAXK];
LL DP1s[MAXN][MAXK], DP2s[MAXN][MAXK];

int get_result(int N, int K) {
  if (K >= MAXK) {
    return 0;
  }

  LL result = 0;
  REP(i,N)REP(k1,MAXK)REP(k2,MAXK) {
    if (max(k1, k2) != K) continue;

    (result += SN[N-1][i] * DP1[i+1][k1] % MOD * DP1[N-i][k2]) %= MOD;
  }

  return result;
}

void verify() {
  REP(i,MAXN) assert(get_result(i,MAXK-1) == 0);

  LL fact = 1;
  FOR(n,1,MAXN) {
    (fact *= n) %= MOD;
    LL s = 0;
    REP(k,MAXK) s += get_result(n, k);
    assert(s % MOD == fact);
    // printf("%d %lld\n", n, fact);
  }
}

int main() {
  int N, K;
  scanf("%d%d%d", &N, &K, &MOD);

  REP(i,MAXN) {
    SN[i][0] = SN[i][i] = 1;
    FOR(j,1,i) SN[i][j] = (SN[i-1][j-1] + SN[i-1][j]) % MOD;
  }

  DP1[1][0] = 1;
  DP2[2][1] = 1;
  FOR(i,1,MAXN) {
    REP(j,i-2) FOR(k,1,MAXK) {
      // int k = (k1 == k2) ? k1 + 1 : max(k1,k2);
      LL combs = DP2[j+2][k-1] * DP2[i-1-j][k-1] + DP2[j+2][k] * DP2s[i-1-j][k-1] + DP2s[j+2][k-1] * DP2[i-1-j][k];
      LL add = combs % MOD * SN[i-3][j];
      (DP2[i][k] += add) %= MOD;
    }

    REP(j,i-1) FOR(k,1,MAXK) {
      // int k = max(k1, k2);
      LL combs = DP1[j+1][k] * DP2[i-j][k] + DP1s[j+1][k-1] * DP2[i-j][k] + DP1[j+1][k] * DP2s[i-j][k-1];
      LL add = combs % MOD * SN[i-2][j];
      (DP1[i][k] += add) %= MOD;
    }

    DP1s[i][0] = DP1[i][0];
    FOR(k,1,MAXK) DP1s[i][k] = (DP1s[i][k-1] + DP1[i][k]) % MOD;
    DP2s[i][0] = DP2[i][0];
    FOR(k,1,MAXK) DP2s[i][k] = (DP2s[i][k-1] + DP2[i][k]) % MOD;
  }

  // verify();
  printf("%d\n", get_result(N, K));
}