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

using namespace std;

long long result[1005][15];
long long jeden[1005][15];
long long dwa[1005][15];

long long jeden_do[1005][15];
long long dwa_do[1005][15];

long long BiNom[1005][1005];

int potegi[15];

int n, k;
long long p, teraz;

int log_sufit (int N)
{
	int potega = 1;
	int wynik = 0;
	while (potega < N)
	{
		potega *= 2;
		wynik++;
	}
	return wynik;
}

int main ()
{
	potegi[0] = 1;
	for (int i = 1; i < 15; ++i) potegi[i] = 2 * potegi[i - 1];
	scanf("%d%d%lld", &n, &k, &p);
	if (k > log_sufit(n))
	{
		printf("0\n");
		return 0;
	}
	for (int i = 0; i <= 1000; ++i) BiNom[i][0] = 1;
	for (int j = 1; j <= 1000; ++j) for (int i = j; i <= 1000; ++i) BiNom[i][j] = (BiNom[i - 1][j - 1] + BiNom[i - 1][j]) % p;
	result[1][1]= 1;
	for (int i = 2; i <= n; ++i) result[i][1] = (result[i - 1][1] * 2) % p;
	for (int i = 1; i <= n; ++i) jeden_do[i][1] = jeden[i][1] = 1;
	dwa_do[2][1] = dwa[2][1] = 1;
	for (int j = 2; j <= k; ++j)
	{
		for (int i = 2; i <= potegi[j - 1]; ++i)
		{
			dwa_do[i][j] = dwa_do[i][j - 1];
			jeden_do[i][j] = jeden_do[i][j - 1];
		}
		for (int i = potegi[j - 1] + 1; i <= n; ++i)
		{
			for (int m = 2; m < i; ++m)
			{
			 	teraz = dwa[m][j - 1] * dwa[i - m + 1][j - 1] + dwa[m][j] * dwa_do[i - m + 1][j - 1] + dwa_do[m][j - 1] * dwa[i - m + 1][j];
				teraz %= p;
				dwa[i][j] += BiNom[i - 3][m - 2] * teraz;
				dwa[i][j] %= p;
			}
			dwa_do[i][j] = (dwa_do[i][j - 1] + dwa[i][j]) % p;
			jeden[i][j] = dwa[i][j];
			for (int m = 2; m < i; ++m)
			{
			 	teraz = jeden[m][j] * dwa_do[i - m + 1][j] + jeden_do[m][j - 1] * dwa[i - m + 1][j];
				teraz %= p;
				jeden[i][j] += BiNom[i - 2][m - 1] * teraz;
				jeden[i][j] %= p;
			}
			jeden_do[i][j] = (jeden_do[i][j - 1] + jeden[i][j]) % p;
			result[i][j] = (2 * jeden[i][j]) % p;
			for (int m = 2; m < i; ++m)
			{
			 	teraz = jeden[m][j] * jeden_do[i - m + 1][j] + jeden_do[m][j - 1] * jeden[i - m + 1][j];
				teraz %= p;
				result[i][j] += BiNom[i - 1][m - 1] * teraz;
				result[i][j] %= p;
			}
		}
	}
	printf("%lld\n", result[n][k]);
	return 0;
}