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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = (1ll<<60);
ll fast_pow(int a, int k)
{
	if (k == 0)
		return 1;
	return fast_pow((a*a), k/2) * ((k % 2 == 0) ? 1 : a);
}
void __exit(ll ans)
{
	cout << ans <<endl;
	exit(0);
}
int get_ans(int n, int P[])
{
	if (n == 1)
		return 0;
	vector <int> V, W;
	for (int i = 0; i < n; i++)
		if ((i-1 < 0 || P[i-1] < P[i]) && (i+1 >= n || P[i+1] < P[i])) 
			V.push_back(P[i]);
	int ans = 1;
	while (V.size() > 1) {
		ans++;
		n = V.size();
		for (int i = 0; i < n; i++)
			if ((i-1 < 0 || V[i-1] < V[i]) && (i+1 >= n || V[i+1] < V[i])) 
				W.push_back(V[i]);
		V = W;
		W.clear();
	}
	return ans;
}
void solve_for_n_to_10(ll n, ll k, ll q)
{
	int P[n];
	for (int i = 0; i < n; i++)
		P[i] = i;
	ll ans = 0;
	do {
		if (get_ans(n, P) == k)
			ans++;
	}
	while (next_permutation(&P[0], &P[n]));
	__exit(ans % q);
}
void solve_for_greater_n(ll n, ll k, ll q)
{
	ll Sil[n+1];
	Sil[0] = Sil[1] = 1;
	for (int i = 2; i <= n; i++)
		Sil[i] = (Sil[i-1] * i) % q;
	vector < vector <ll> > D(n+1, vector <ll> (k+1, 0)), O(n+1, vector <ll> (n+1, 0));
	/* O[i][j] - na ile sposobów można obudować i elementami j większych elementów */
	D[1][0] = 1;
	//D[2][1] = 2;
	//O[0][0] = 1;
	O[0][1] = 1;
	O[1][1] = 2;
	O[1][2] = 1;
	/*O[2][1] = 4;
	O[2][2] = 2+2*2;
	O[2][3] = 2;*/
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			for (int l = 1; l < i; l++) {
				if (j > 1)
					D[i][j] += D[i-l][j] * O[l][1];
				D[i][j] = (D[i][j] + D[l][j-1] * ((O[i-l][l]) % q)) % q;
				//cout << i << " " << j << " " << l << " | " << D[l][j-1] << " " << O[i-l][l] <<endl;				
			}
		}
		//O[i][1] = (O[i-1][1] * 2) % q;
		for (int l = 1; l <= i; l++) {
			O[i][l] = (O[i-1][l] * (2*l) + O[i-1][l-1] * (l-1)) % q;
			//cout << i << " " << l << "  " << O[i][l] <<endl;
		}
		O[i][i+1] = Sil[i];
	}
	__exit(D[n][k]);
}
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll n, k, q;
	cin >> n >> k >> q;
	if (k > 30 || fast_pow(2, k) > 2 * n)
		__exit(0);
	if (n <= 11) {
		solve_for_n_to_10(n, k, q);
	}
	else {
		solve_for_greater_n(n, k, q);
	}
	return 0;
}