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

#define nizej 0
#define wyzej 1
#define rowno 2

#define zwykla 0
#define mnozona 1

using namespace std;

int n, m, p;
int dp[2][5000005][3], sum[3][5000005][2][2];
int getsum(int pref, int l, int r, int kejs, int ktora) {
	int result = sum[pref][r][kejs][ktora] - sum[pref][l - 1][kejs][ktora];
	if(result < 0) result += p;
	return result;
}
int32_t main() {
	cin >> n >> m >> p;
	if(n == 1) {
		cout << (1LL * m * (m + 1) / 2) % p;
		return 0;
	}
	for(int i = 1; i <= m; i++) {
		dp[1][i][wyzej] = 1;
		sum[1][i][wyzej][zwykla] = i;
	}

	int pref = 1;
	for(int kek = 2; kek <= n; kek++) {
		pref = !pref;
		for(int wys3 = 1; wys3 <= m; wys3++) {
			dp[pref][wys3][wyzej] = 1LL * (getsum(1 - pref, wys3 + 1, m, wyzej, zwykla) + getsum(1 - pref, wys3 + 1, m, wyzej, mnozona)) * wys3 % p;
			/*for(int wys2 = wys3 + 1; wys2 <= m; wys2++) {
				// wys1 > wys2 > wys3
				dp[pref][wys3][wyzej] += dp[pref - 1][wys2][wyzej] * wys3;
				dp[pref][wys3][wyzej] %= p;
				// wys1 = wys2 > wys3
				dp[pref][wys3][wyzej] += (dp[pref - 1][wys2][rowno] * (m - wys2 + 1) % p) * wys3;
				dp[pref][wys3][wyzej] %= p;
			}*/
			dp[pref][wys3][nizej] = 1LL * (getsum(1 - pref, 1, wys3 - 1, nizej, zwykla) + getsum(1 - pref, 1, wys3 - 1, nizej, mnozona)) * (m - wys3 + 1) % p;
			/*
			for(int wys2 = 1; wys2 < wys3; wys2++) {
				// wys1 < wys2 < wys3
				dp[pref][wys3][nizej] += dp[pref - 1][wys2][nizej] * (m - wys3 + 1);
				dp[pref][wys3][nizej] %= p;
				// wys1 = wys2 < wys3
				dp[pref][wys3][nizej] += (dp[pref - 1][wys2][rowno] * wys2 % p) * (m - wys3 + 1);
				dp[pref][wys3][nizej] %= p;
			}
			*/
			// wys1 = wys2 = wys3
			dp[pref][wys3][rowno] = 1LL * (1LL * dp[1 - pref][wys3][rowno] * wys3 % p) * (m - wys3 + 1) % p;
			// wys1 > wys2 = wys3
			dp[pref][wys3][rowno] += 1LL * dp[1 - pref][wys3][wyzej] * wys3 % p;
			if(dp[pref][wys3][rowno] >= p)
				dp[pref][wys3][rowno] -= p;
			//wys1 < wys2 = wys3
			dp[pref][wys3][rowno] += 1LL * dp[1 - pref][wys3][nizej] * (m - wys3 + 1) % p;
			if(dp[pref][wys3][rowno] >= p)
				dp[pref][wys3][rowno] -= p;

			sum[pref][wys3][wyzej][zwykla] = (dp[pref][wys3][wyzej] + sum[pref][wys3 - 1][wyzej][zwykla]) % p;
			sum[pref][wys3][wyzej][mnozona] = (1LL * dp[pref][wys3][rowno] * (m - wys3 + 1) + sum[pref][wys3 - 1][wyzej][mnozona]) % p;

			sum[pref][wys3][nizej][zwykla] = (dp[pref][wys3][nizej] + sum[pref][wys3 - 1][nizej][zwykla]) % p;
			sum[pref][wys3][nizej][mnozona] = (1LL * dp[pref][wys3][rowno] * wys3 + sum[pref][wys3 - 1][nizej][mnozona]) % p;
			//	for(int i = 0; i < 3; i++) cout << dp[pref][wys3][i] << " ";
		//	for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) cout << sum[pref][wys3][i][j] << " ";
		//	cout << "\n";
		}

	}

	int res = 0;
	for(int wys = 1; wys <= m; wys++) {
		res += 1LL * (1LL * dp[pref][wys][rowno] * wys % p) * (m - wys + 1) % p;
		if(res >= p) res -= p;
		res += 1LL * wys * dp[pref][wys][wyzej] % p;
		if(res >= p) res -= p;
		res += 1LL * (m - wys + 1) * dp[pref][wys][nizej] % p;
		if(res >= p) res -= p;
	}

	cout << res;
}