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
#include <cstdio>

#define mmm(x) ((x) % mod)

long long dpL[1007][12], dpLR[1007][12];
long long nk[1007][1007];

int main() {
    int N, K, mod;
    scanf("%d%d%d", &N, &K, &mod);
    if (K > 10) {
        printf("0");
        return 0;
    }
    if (N == 1) {
        printf("0");
        return 0;
    }
    nk[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        nk[i][0] = 1;
        for (int w = 1; w <= i; w++)
            nk[i][w] = (nk[i - 1][w - 1] + nk[i - 1][w]) % mod;
    }
    for (int k = 1; k < 11; k++) {
        dpL[1][k] = 1;
        dpLR[1][k] = 1;
    }
    for (int i = 2; i < N; i++) {
        for (int k = 1; k < 11; k++) {
            dpL[i][k] = dpL[i][k - 1];
            dpLR[i][k] = dpLR[i][k - 1];

            dpL[i][k] += dpL[i - 1][k] - dpL[i - 1][k - 1];
            dpL[i][k] += dpLR[i - 1][k - 1] - dpLR[i - 1][k - 2];
            dpL[i][k] %= mod;
            for (int w = 2; w < i; w++) {
                dpL[i][k] += mmm(mmm((dpLR[w - 1][k - 1] - dpLR[w - 1][k - 2]) * dpL[i - w][k]) * nk[i - 1][w - 1]);
                dpL[i][k] += mmm(mmm(dpLR[w - 1][k - 2] * (dpL[i - w][k] - dpL[i - w][k - 1])) * nk[i - 1][w - 1]);
                dpL[i][k] %= mod;
            }

            dpLR[i][k] += dpLR[i - 1][k] - dpLR[i - 1][k - 1];
            dpLR[i][k] += dpLR[i - 1][k] - dpLR[i - 1][k - 1];
            dpLR[i][k] %= mod;
            for (int w = 2; w < i; w++) {
                dpLR[i][k] += mmm(mmm((dpLR[w - 1][k - 1] - dpLR[w - 1][k - 2]) * (dpLR[i - w][k - 1] - dpLR[i - w][k - 2])) * nk[i - 1][w - 1]);
                dpLR[i][k] += mmm(mmm(dpLR[w - 1][k - 1] * (dpLR[i - w][k] - dpLR[i - w][k - 1])) * nk[i - 1][w - 1]);
                dpLR[i][k] += mmm(mmm((dpLR[w - 1][k] - dpLR[w - 1][k - 1]) * dpLR[i - w][k - 1]) * nk[i - 1][w - 1]);
                dpLR[i][k] %= mod;
            }
        }
    }
    long long wyn = 0;
    wyn += 2 * (dpL[N - 1][K] - dpL[N - 1][K - 1]);
    wyn %= mod;
    for (int w = 2; w < N; w++) {
        wyn += mmm(mmm((dpL[w - 1][K] - dpL[w - 1][K - 1]) * dpL[N - w][K]) * nk[N - 1][w - 1]);
        wyn += mmm(mmm(dpL[w - 1][K - 1] * (dpL[N - w][K] - dpL[N - w][K - 1])) * nk[N - 1][w - 1]);
        wyn %= mod;
    }
    printf("%lld\n", mmm(wyn + mod));
    return 0;
}