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
#include <cstdio>
using namespace std;
typedef long long LL;

const int MAXN = 1000;
const int MAXK = 10;

int N, K, P;
LL b[MAXN+1][MAXN+1];
LL D[MAXN+1][MAXK+1], L[MAXN+1][MAXK+1], S[MAXN+1][MAXK+1];
LL Ds[MAXN+1][MAXK+1], Ls[MAXN+1][MAXK+1];

void show(LL t[][MAXK+1], int I, int J) {
	for (int i=0; i<=I; ++i) {
		for (int j=0; j<=J; ++j) printf("%d ", t[i][j]);
		puts("");
	}
}

int main() {
	b[0][0] = D[0][0] = L[0][0] = S[1][0] = 1;
	for (int i=0; i<=MAXK; ++i) Ds[0][i] = Ls[0][i] = 1;
	
	scanf("%d%d%d", &N, &K, &P);
	for (int i=1; i<=N; ++i) for (int j=0; j<=i; ++j) b[i][j] = (b[i-1][j-1] + b[i-1][j]) % P;
	
	for (int n=1; n<=N; ++n) for (int k=1; k<=MAXK; ++k) {
		for (int i=0, j=n-1; i<=n-1; ++i, --j) {
			LL x = (D[i][k]*Ds[j][k-1] + Ds[i][k-1]*D[j][k] + D[i][k-1]*D[j][k-1]) % P;
			D[n][k] += b[n-1][i] * x % P;
			LL y = (D[i][k-1]*Ls[j][k-1] + Ds[i][k-1]*L[j][k]) % P;
			L[n][k] += b[n-1][i] * y % P;
			LL z = (L[i][k]*Ls[j][k-1] + Ls[i][k-1]*L[j][k] + L[i][k]*L[j][k]) % P;
			S[n][k] += b[n-1][i] * z % P;
		}
		D[n][k] %= P;
		L[n][k] %= P;
		S[n][k] %= P;
		Ds[n][k] = (Ds[n][k-1] + D[n][k]) % P;
		Ls[n][k] = (Ls[n][k-1] + L[n][k]) % P;
	}
	
	LL res = K>MAXK ? 0 : S[N][K];
	if (res < 0) res += P;
	printf("%lld\n", res);
	
	// puts("D");
	// show(D, 3, 3);
	// puts("L");
	// show(L, 3, 3);
	// puts("S");
	// show(S, 4, 3);
	
	return 0;
}