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
93
94
#include<bits/stdc++.h>
using namespace std;

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> pll;
typedef pair<lli, int> pli;
typedef pair<int, lli> pil;

const int N=1005;
int n, k, mod, pascal[N][N], ile[N];
lli dp[N][N][3];

int32_t main()
{
    boost;
    cin>>n>>k>>mod;
    for(int i=0;i<=n;i++)
    {
        pascal[i][0]=1;
        pascal[i][i]=1;
        for(int j=1;j<i;j++)pascal[i][j]=(pascal[i-1][j]+pascal[i-1][j-1])%mod;
    }
    dp[2][1][2]=1;
    ile[2]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(j==1)
            {
                for(int l=2;l<=i;l++)
                {
                    if(l==i)
                    {
                        for(int m=2;m<i;m++)
                        {
                            int pom=pascal[i-3][m-2];
                            for(int p=1;p<=max(ile[m], ile[i-m+1]);p++)
                            {
                                lli blep=(lli((dp[m][p][2]-dp[m][p-1][2]+mod)%mod)*dp[i-m+1][p-1][2])%mod;
                                blep=blep*pom%mod;
                                dp[i][p][2]=(dp[i][p][2]+blep)%mod;
                                blep=(lli((dp[i-m+1][p][2]-dp[i-m+1][p-1][2]+mod)%mod)*dp[m][p-1][2])%mod;
                                blep=blep*pom%mod;
                                dp[i][p][2]=(dp[i][p][2]+blep)%mod;
                                blep=(lli((dp[m][p][2]-dp[m][p-1][2]+mod)%mod)*((dp[i-m+1][p][2]-dp[i-m+1][p-1][2]+mod)%mod))%mod;
                                blep=blep*pom%mod;
                                dp[i][p+1][2]=(dp[i][p+1][2]+blep)%mod;
                            }
                        }
                    }
                    else
                    {
                        int pom=pascal[i-2][l-2];
                        for(int p=1;p<=max(ile[l], ile[i-l+1]);p++)
                        {
                            lli blep=((lli(dp[l][p][2])*dp[i-l+1][p][1]%mod)-(lli(dp[l][p-1][2])*dp[i-l+1][p-1][1]%mod)+mod)%mod;
                            blep=blep*pom%mod;
                            dp[i][p][1]=(dp[i][p][1]+blep)%mod;
                        }
                    }
                }
            }
            else
            {
                int pom=pascal[i-1][j-1];
                for(int p=1;p<=max(ile[j], ile[i-j+1]);p++)
                {
                    lli blep=((lli(dp[j][p][1])*dp[i-j+1][p][1]%mod)-(lli(dp[j][p-1][1])*dp[i-j+1][p-1][1]%mod)+mod)%mod;
                    blep=blep*pom%mod;
                    dp[i][p][0]=(dp[i][p][0]+blep)%mod;
                }
            }
        }
        for(int j=1;j<=max(i, 20);j++)
        {
            if(dp[i][j][0]+dp[i][j][1]+dp[i][j][2]!=0)ile[i]=j;
            dp[i][j][1]=(dp[i][j][1]+dp[i][j][2])%mod;
            dp[i][j][0]=(dp[i][j][0]+dp[i][j][1]*2)%mod;
            for(int l=0;l<=2;l++)dp[i][j][l]=(dp[i][j][l]+dp[i][j-1][l])%mod;
        }
    }
    lli wyn=(dp[n][k][0]-dp[n][k-1][0]+mod)%mod;
    cout<<wyn<<"\n";
	return 0;
}