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
#include <cstdio>
#define MAXN 1002
#define MK 11
#define lld long long int

using namespace std;

int n, k, m;
int w1[MAXN][MK];
int w2[MAXN][MK];
int nk[MAXN][MAXN];

int main() {
  scanf("%d%d%d", &n, &k, &m);

  // calc "n po k"
  nk[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      nk[i][j] = nk[i - 1][j] + nk[i - 1][j - 1];
      if (nk[i][j] >= m) nk[i][j] -= m;
    }
    nk[i][0] = 1;
  }

  w2[1][1] = w1[1][1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < MK; j++) {
      lld res2 = 0, res1 = 0;
      for (int l = 1; l <= i; l++) {
        lld iml = 0, lm1 = 0, iml1 = 0, lm11 = 0;
        
        for (int p = 1; p < j; p++) {
          lm1  += w2[l - 1][p];
          iml  += w2[i - l][p];
          iml1 += w1[i - l][p];
        }

        if (l - 1 == 0) lm1 = 1;
        if (i - l == 0) iml = iml1 = 1;

        lm11 = lm1  * w1[i - l][j] % m;
        iml1 = iml1 * w2[l - 1][j - 1] % m;
        lm1 =  lm1  * w2[i - l][j] % m;
        iml =  iml  * w2[l - 1][j] % m;

        res2 = (res2 + (lm1  + iml  + (lld)w2[i - l][j - 1] * w2[l - 1][j - 1])
          % m * nk[i - 1][l - 1]) % m;
        res1 = (res1 + (lm11 + iml1) * nk[i - 1][l - 1]) % m;
      }
      
      w2[i][j] = res2 % m;
      w1[i][j] = res1 % m;
    }
  }
  lld res = 0;
  if (k > 10) {
    printf("0\n");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    lld l = 0, r = 0;
    for (int j = 1; j < k; j++) {
      l += w1[i - 1][j];
      r += w1[n - i][j];
    }
    r = (r + w1[n - i][k]) % m;

    if (i - 1 == 0) l = 1;
    if (n - i == 0) r = 1;

    l = l * w1[n - i][k] % m;
    r = r * w1[i - 1][k] % m;

    res = (res + (l + r) * nk[n - 1][i - 1]) % m;
  }
  printf("%lld\n", res);
  return 0;
}