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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int MAXM = 10000000;

int m, p;
int a[MAXM], b[MAXM];

inline void Add(int &x, int y) {
	x += y;
	if (x >= p) x -= p;
}

inline void Sub(int &x, int y) {
	x -= y;
	if (x < 0) x += p;
}

void Step() {
	for (int i = 0; i < m; i++)
		b[i] = a[m - 1];
	for (int i = 1; i < m; i++)
		Add(b[i], b[i - 1]);
		
	for (int i = 0; i < m - 1; i++)
		Sub(b[i], a[m - 2 - i] * ll(i + 1) % p);
	int d = 0;
        for (int i = 1; i < m; i++) {
		Add(d, a[i - 1]);
		Sub(b[i], d);
	}
	a[0] = b[0];
        for (int i = 1; i < m; i++) {
		a[i] = b[i];
		Add(a[i], a[i - 1]);
	}
}

int n;

int Solve() {
	a[m - 1] = 1;
	for (int i = 0; i < m - 1; i++)
		a[i] = 0;
	for (int i = 0; i < n; i++)
		Step();
	return a[m - 1];
}

int main() {
	scanf("%d%d%d", &n, &m, &p);
	printf("%d\n", Solve());
	return 0;
}