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 <cstdio>

int n, k;
long long p, t2[1001][1001], t2_sum[1001][1001], t1[1001][1001], t1_sum[1001][1001], t[1001][1001], c[1001][1001];

int main() {
	scanf("%d%d%lld", &n, &k, &p);

	for (int m = 0; m <= n; m++) {
		for (int k = 0; k <= m; k++) {
			if (k == 0 || k == m) {
				c[m][k] = 1;
			} else {
				c[m][k] = (c[m-1][k-1] + c[m-1][k]) % p;
			}
		}
	}
	
	t2[1][0] = t2[2][1] = 1;
	t2_sum[1][0] = 1;
	for (int i = 1; i <= k; i++) {
		t2_sum[1][i] = t2_sum[2][i] = 1;
	}
	for (int m = 3; m <= n; m++) {
		t2[m][1] = 0;
		int i;
		for (i = 2; i <= k; i++) {
			for (int j = 2; j < m; j++) {
				long long part = c[m-3][j-2] * (
					(t2[j][i-1] * t2[m-j+1][i-1]) % p +
					(t2[j][i] * t2_sum[m-j+1][i-1]) % p +
					(t2_sum[j][i-1] * t2[m-j+1][i]) % p
				) % p;
				t2[m][i] = (t2[m][i] + part) % p;

			}
			if (t2[m][i] == 0 && t2[m][i-1] == 0)
				break;
			t2_sum[m][i] = (t2_sum[m][i-1] + t2[m][i]) % p;
		}
		for (; i <= k; i++)
			t2_sum[m][i] = (t2_sum[m][i-1] + t2[m][i]) % p;

	}

	t1[1][0] = 1;
	for (int i = 0; i <= k; i++) {
		t1_sum[1][i] = 1;
	}
	for (int m = 2; m <= n; m++) {
		t1[m][1] = t1_sum[m][1] = 1;
		int i;
		for (i = 2; i <= k; i++) {
			for (int j = 2; j <= m; j++) {
				long long part = c[m-2][j-2] * (
						(t2[j][i] * t1_sum[m-j+1][i]) % p +
						(t2_sum[j][i-1] * t1[m-j+1][i]) % p
				) % p;
				t1[m][i] = (t1[m][i] + part) % p;
			}
			if (t1[m][i] == 0 && t1[m][i-1] == 0)
				break;
			t1_sum[m][i] = (t1_sum[m][i-1] + t1[m][i]) % p;
		}
		for (; i <= k; i++)
			t1_sum[m][i] = (t1_sum[m][i-1] + t1[m][i]) % p;
	}

	t[1][0] = 1;
	for (int m = 2; m <= n; m++) {
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= n; j++) {
				long long part = c[m-1][j-1] * (
						(t1[j][i] * t1_sum[m-j+1][i]) % p +
						(t1_sum[j][i-1] * t1[m-j+1][i]) % p
				) % p;
				t[m][i] = (t[m][i] + part) % p;
			}
			if (i > 3 && t[m][i] == 0 && t[m][i-1] == 0)
				break;
		}
	}

	printf("%lld\n", t[n][k]);

}