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
#include <bits/stdc++.h>
#define f first
#define s second
#define LL long long
#define ALL(V) V.begin(),V.end()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
#define debug(x) cerr<<#x<<": "<<x<<endl
using namespace std;
const LL N=1e3+9;
unsigned long long p;
unsigned long long dwu[N][N];
unsigned long long dp[N][15][3];
void gemacht(int n) {
    if(n==0) {
        for(int j=0;j<3;j++) {
            dp[n][0][j]=1;
        }
        return;
    }
    if(n==1) {
        for(int j=0;j<3;j++) {
            dp[n][1][j]=1;
        }
        return;
    }
    int ile=log2(n)+2;
    for(int i=0;i<n;i++) {
        for(int j=0;j<ile;j++) {
            for(int k=0;k<ile;k++) {
                int akt1=max(j,k);
                if(j==k) akt1++;
                int akt2=max(j+1,k);
                int akt3=max(j,k+1);
                dp[n][akt1][0]+=dwu[n-1][i]*((dp[n-i-1][j][0]*dp[i][k][0])%p);
                dp[n][akt2][1]+=dwu[n-1][i]*((dp[n-i-1][j][0]*dp[i][k][1])%p);
                dp[n][akt3][2]+=dwu[n-1][i]*((dp[n-i-1][j][2]*dp[i][k][0])%p);
            }
        }
        for(int j=0;j<ile+1;j++) {
            if(dp[n][j][0]>p) dp[n][j][0]%=p;
            if(dp[n][j][1]>p) dp[n][j][1]%=p;
            if(dp[n][j][2]>p) dp[n][j][2]%=p;
        }
    }
}
int32_t main(void) {
    int n,kW;
    cin>>n>>kW>>p;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=i;j++) {
            if(i==j||j==0) {
                dwu[i][j]=1;
                continue;
            }
            dwu[i][j]=dwu[i-1][j]+dwu[i-1][j-1];
            dwu[i][j]%=p;
        }
    }
    for(int i=0;i<n;i++) gemacht(i);
    long long wynik=0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<11;j++) {
            for(int k=0;k<11;k++) {
                if(max(j,k)==kW) wynik+=dwu[n-1][i]*((dp[n-i-1][j][1]*dp[i][k][1])%p);
                wynik%=p;
            }
        }
    }
    cout<<wynik<<endl;
}