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
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int N=1005,inf=10,M=inf+1;
int n,m,mod,binom[N][N],cm[N][2];
int c1[N],c0[N];
int f[N][M][2];
bool vi[N][M][2];
int dfs(int n,int k,int c){
	if(n==0||k==0)return n==0&&k==0;
	if(k>cm[n][c])return 0;
	if(vi[n][k][c])return f[n][k][c];
	int x,k1,k2,l,r,v,s=0;i64 ts;
	if(c==1){
		for(x=1;x<=n;++x){
			l=x-1,r=n-x,v=binom[n-1][x-1];
			k1=k;
			if(k1<=cm[l][1]){
				for(ts=k2=0;k2<k&&k2<=cm[r][0];++k2)ts+=dfs(r,k2,0);
				s=(s+ts%mod*dfs(l,k1,1)%mod*v)%mod;
			}
			k2=k-1;
			if(k2<=cm[r][0]){
				for(ts=k1=0;k1<k&&k1<=cm[l][1];++k1)ts+=dfs(l,k1,1);
				s=(s+ts%mod*dfs(r,k2,0)%mod*v)%mod;
			}
		}
	}else{
		for(x=1;x<=n;x++){
			l=x-1,r=n-x,v=binom[n-1][x-1];
			if(k-1<=cm[min(l,r)][0]){
				s=(s+(i64)dfs(l,k-1,0)*dfs(r,k-1,0)%mod*v)%mod;
			}
			if(k<=cm[l][0]){
				for(k1=k,ts=k2=0;k2<k&&k2<=cm[r][0];++k2)ts+=dfs(r,k2,0);
				s=(s+(i64)2*ts%mod*dfs(l,k1,0)%mod*v)%mod;
			}
		}
	}
//	cerr<<" n = "<<n<<", k = "<<k<<", c = "<<c<<", s = "<<s<<endl;
	return vi[n][k][c]=true,f[n][k][c]=s;
}
int main(){
	int i,j,k1,k2,s=0;
	scanf("%d%d%d",&n,&m,&mod);
	if(m>=inf)puts("0"),exit(0);
	for(i=1;i<=n;i++)cm[i][1]=cm[i>>1][1]+1,cm[i][0]=cm[(i-1)>>1][0]+1;
	for(i=0;i<=n;i++)for(j=binom[i][0]=1;j<=i;j++)binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%mod;
	for(k1=0;k1<=m;k1++)for(k2=0;k2<=m;k2++){
		if(max(k1,k2)!=m)continue; 
		for(i=1;i<=n;i++)s=(s+(i64)dfs(i-1,k1,1)*dfs(n-i,k2,1)%mod*binom[n-1][i-1])%mod;
	}
	printf("%d\n",s);
}