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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
/*  0 -> normalnie
 *  1 -> zawsze pęka z lewej
 *  2 -> zawsze pęka z prawej
 *  3 -> zawsze pęka z obu
 */
long long dp[1010][20][5];
int sum[1010][20][5]; //suma[x][y][z]= i=1 -> y dp[x][i][z]
int wspol[1010][1010]; // n po k
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k,p,i,j,x;
	long long a;
	cin>>n>>k>>p;
	if(k>log2(n)+1)
	{
		cout<<"0";
		return 0;
	}
	wspol[1][0]=1;
	wspol[1][1]=1;
	for(i=2;i<=n;i++)
	{
		wspol[i][0]=1;
		for(j=1;j<=i;j++)
		{
			wspol[i][j]=(wspol[i-1][j-1]+wspol[i-1][j])%p;
			//cout<<i<<" po "<<j<<" = "<<wspol[i][j]<<"\n";
		}
	}
	dp[0][0][0]=1;
	dp[0][0][1]=1;
	dp[0][0][2]=1;
	dp[0][0][3]=1;
	dp[1][0][0]=1;
	dp[1][1][1]=1;
	dp[1][1][2]=1;
	dp[1][1][3]=1;
	sum[1][0][0]=1;
	for(i=0;i<=k;i++)
	{
		for(j=0;j<=3;j++)
			sum[0][i][j]=1;
	}
	for(i=1;i<=k;i++)
	{
		for(j=0;j<=3;j++)
			sum[1][i][j]=1;
	}
	for(i=2;i<=n;i++)
	{
		for(j=1;j<=k;j++)
		{
			// x z lewej
			for(x=0;x<i;x++)
			{
				if((i==n)&&(j==k))
				{
					// 0
					// z lewej j z prawej mniej
					//dp[i][j][0]=(dp[i][j][0]+(((dp[x][j][2]*sum[i-x-1][j-1][1])%p)*wspol[i-1][x])%p)%p;
					a=dp[x][j][2]*sum[i-x-1][j-1][1];
					// z lewej mniej z prawej j
					//dp[i][j][0]=(dp[i][j][0]+(((sum[x][j-1][2]*dp[i-x-1][j][1])%p)*wspol[i-1][x])%p)%p;
					a+=sum[x][j-1][2]*dp[i-x-1][j][1];
					// oba j
					//dp[i][j][0]=(dp[i][j][0]+(((dp[x][j][2]*dp[i-x-1][j][1])%p)*wspol[i-1][x])%p)%p;
					a+=dp[x][j][2]*dp[i-x-1][j][1];
					dp[i][j][0]=(dp[i][j][0]+wspol[i-1][x]*(a%p))%p;
				}
				
				// 1
				// z lewej j-1 z prawej mniej lub równo j
				//dp[i][j][1]=(dp[i][j][1]+(((dp[x][j-1][3]*sum[i-x-1][j][1])%p)*wspol[i-1][x])%p)%p;
				a=dp[x][j-1][3]*sum[i-x-1][j][1];
				// z lewej mniej niż j-1 z prawej j
				//dp[i][j][1]=(dp[i][j][1]+(((sum[x][j-2][3]*dp[i-x-1][j][1])%p)*wspol[i-1][x])%p)%p;
				a+=sum[x][j-2][3]*dp[i-x-1][j][1];
				dp[i][j][1]=(dp[i][j][1]+wspol[i-1][x]*(a%p))%p;
				
				/*
				// 2
				// z lewej mniej lub równo j z prawej j-1 
				dp[i][j][2]=(dp[i][j][2]+(((sum[x][j][2]*dp[i-x-1][j-1][3])%p)*wspol[i-1][x])%p)%p;
				// z lewej j z prawej mniej niż j-1
				dp[i][j][2]=(dp[i][j][2]+(((dp[x][j][2]*sum[i-x-1][j-2][3])%p)*wspol[i-1][x])%p)%p;
				*/
				
				// 3
				// z lewej j z prawej mniej
				//dp[i][j][3]=(dp[i][j][3]+(((dp[x][j][3]*sum[i-x-1][j-1][3])%p)*wspol[i-1][x])%p)%p;
				a=dp[x][j][3]*sum[i-x-1][j-1][3];
				// z lewej mniej z prawej j
				//dp[i][j][3]=(dp[i][j][3]+(((sum[x][j-1][3]*dp[i-x-1][j][3])%p)*wspol[i-1][x])%p)%p;
				a+=sum[x][j-1][3]*dp[i-x-1][j][3];
				// oba j-1
				//dp[i][j][3]=(dp[i][j][3]+(((dp[x][j-1][3]*dp[i-x-1][j-1][3])%p)*wspol[i-1][x])%p)%p;
				a+=dp[x][j-1][3]*dp[i-x-1][j-1][3];
				dp[i][j][3]=(dp[i][j][3]+wspol[i-1][x]*(a%p))%p;
				
			}
			dp[i][j][2]=dp[i][j][1];
			//sum[i][j][0]=sum[i][j-1][0]+dp[i][j][0];
			sum[i][j][1]=(sum[i][j-1][1]+dp[i][j][1])%p;
			sum[i][j][2]=(sum[i][j-1][2]+dp[i][j][2])%p;
			sum[i][j][3]=(sum[i][j-1][3]+dp[i][j][3])%p;
			//cout<<"dp["<<i<<"]["<<j<<"] [1]="<<dp[i][j][1]<<" [2]="<<dp[i][j][2]<<" [3]="<<dp[i][j][3]<<"\n";
		}
	}
	cout<<dp[n][k][0];
	return 0;
}