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
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define PR std::pair
#define MP std::make_pair
#define X first
#define Y second
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

int MOD;
inline int D(int a, int b){
	return (a + b >= MOD ? a + b - MOD : a + b);
}
inline int O(int a, int b){
	return (a - b < 0 ? a - b + MOD : a - b);
}
inline int M(int a, int b){
	return (1ll*a*b)%MOD;
}

const int N = 10000006;
int pup[N];
int pdown[N];
int cup[N];
int cdown[N];
int up[N];
int down[N];
int all;

int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m >> MOD;

	auto calc_pref = [&](){
		for(int i = m; i >= 1; --i) pup[i] = D(pup[i+1], up[i]);
		for(int i = m-1; i >= 1; --i) cup[i] = D(cup[i+1], pup[i+1]);

		REP(i, 1, m+1) pdown[i] = D(pdown[i-1], down[i]);
		REP(i, 2, m+1) cdown[i] = D(cdown[i-1], pdown[i-1]);

		all = 0;
		REP(i, 1, m+1) all = D(all, up[i]);
	};

	up[1] = 1;
	down[m] = 1;
	calc_pref();
	REP(j, 1, n+1){
		REP(i, 1, m+1){
			int ile = m-i+1;
			up[i] = M(O(all, pdown[i-1]), ile);
			up[i] = O(up[i], cup[i]);

			ile = i;
			down[i] = M(O(all, pup[i+1]), ile);
			down[i] = O(down[i], cdown[i]);
		}
		calc_pref();
	}

	std::cout << all << "\n";

	return 0;
}