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
91
92
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, k, M;
int fact[N], factInv[N];
int dp[N][N][2], pref[N][N][2];
int pascal[N][N];

void add(int &w, int u) {
    w += u;
    if (w >= M) w -= M;
    if (w < 0) w += M;
}

int mul(int w, int u) {
    return (long long)w * u % M;
}

int newton(int n, int k) {
    if (k < 0 || k > n) return 0;
    return pascal[n][k];
}

int main() {
    
    scanf("%d %d %d", &n, &k, &M);
    k = min(k, 11);
    
    for (int i = 0; i <= n; i++) {
        pascal[i][i] = pascal[i][0] = 1;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
            if (pascal[i][j] >= M) {
                pascal[i][j] -= M;
            }
        }
    }
    
    dp[0][0][0] = pref[0][0][0] = 1;
    dp[0][1][1] = pref[0][1][1] = 1;
    
    for (int i = 1; i <= k; i++) {
        pref[0][i][0] += pref[0][i - 1][0];
        pref[0][i][1] += pref[0][i - 1][1];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int ile = 0; ile < i; ile++) {
                // For 0
                int goodCombinations = 0;
                add(goodCombinations, mul(dp[ile][j][1], pref[i - ile - 1][j][0]));
                add(goodCombinations, mul(pref[ile][j][1], dp[i - ile - 1][j][0]));
                add(goodCombinations, -mul(dp[ile][j][1], dp[i - ile - 1][j][0]));
                add(dp[i][j][0], mul(newton(i - 1, ile), goodCombinations));
                
                // For 1
                goodCombinations = 0;
                add(goodCombinations, mul(dp[ile][j][1], pref[i - ile - 1][j - 1][1]));
                add(goodCombinations, mul(pref[ile][j - 1][1], dp[i - ile - 1][j][1]));
                add(goodCombinations, mul(dp[ile][j - 1][1], dp[i - ile - 1][j - 1][1]));
                add(dp[i][j][1], mul(newton(i - 1, ile), goodCombinations));
            }

            pref[i][j][0] = pref[i][j - 1][0] + dp[i][j][0];
            if (pref[i][j][0] >= M) pref[i][j][0] -= M;
            pref[i][j][1] = pref[i][j - 1][1] + dp[i][j][1];
            if (pref[i][j][1] >= M) {
                pref[i][j][1] -= M;
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int goodCombinations = 0;
        add(goodCombinations, mul(dp[i][k][0], pref[n - 1 - i][k][0]));
        add(goodCombinations, mul(pref[i][k][0], dp[n - 1 - i][k][0]));
        add(goodCombinations, -mul(dp[i][k][0], dp[n - 1 - i][k][0]));
        add(ans, mul(newton(n - 1, i), goodCombinations));
    }
    
    printf("%d\n", ans);

    return 0;
}