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

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0);

	int n, k, p;
	cin >> n >> k >> p;

	vector<vector<int>> bi(n+1, vector<int>(n+1, 0));

	bi[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		bi[i][0] = bi[i][i] = 1;
		for (int j = 1; j < i; j++) {
			bi[i][j] = ((ll)bi[i-1][j] + bi[i-1][j-1]) % p;
		}
	}

	vector<vector<vector<int>>> a(n, vector<vector<int>>(min(n, k+1), vector<int>(2, 0)));
	vector<vector<int>> b(n, vector<int>(k+1, 0));

	a[1][1][0] = a[1][1][1] = 1;
	b[1][1] = 1;

	for (int i = 2; i < n; i++) {
		for (int j = 1; j <= min(i, k); j++) {
			ll x = a[i-1][j][0];

			for (int l = 1; l < i-1; l++) {
				x = (x + (ll)a[l][j-1][1] * b[i-1-l][j-1] * bi[i-1][l]) % p;
			}

			x += a[i-1][j-1][1];
			a[i][j][0] = x % p;
			b[i][j] = ((ll)b[i][j-1] + x) % p;

			x = (2 * a[i-1][j][1]) % p;

			for (int l = 1; l < i-1; l++) {
				x = (x + (ll)a[l][j-1][1] * a[i-1-l][j-1][1] * bi[i-1][l]) % p;
			}

			a[i][j][1] = x;
		}
	}


	ll res = (2 * a[n-1][k][0]) % p;

	for (int l = 1; l < n-1; l++) {
		ll tmpr = 0;
		tmpr += (ll)a[l][k][0] * a[n-1-l][k][0];
		tmpr %= p;
		tmpr += (ll)a[l][k][0] * b[n-1-l][k-1];
		tmpr %= p;
		tmpr += (ll)b[l][k-1] * a[n-1-l][k][0];
		tmpr %= p;
		res = (res + (ll)bi[n-1][l] * tmpr) % p;
	}

	cout << res << endl;

	return 0;
}