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
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(long long a = 0; a < (b); ++a)
const int LIM=1e7+7;
long long dpre[LIM], dsuf[LIM], pre[LIM], suf[LIM], sumpre[LIM], sumsuf[LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	long long n, m, MOD;
	cin >> m >> n >> MOD; --m;
	rep(i, n) {
		dpre[i]=i+1;
		dsuf[n-i-1]=i+1;
		pre[i]=dpre[i];
		suf[n-i-1]=dsuf[n-i-1];
		if(i) {
			suf[n-i-1]+=suf[n-i];
			pre[i]+=pre[i-1];
		}
		suf[n-i-1]%=MOD;
		pre[i]%=MOD;
		sumpre[i]=pre[i];
		sumsuf[n-i-1]=suf[n-i-1];
		if(i) {
			sumpre[i]+=sumpre[i-1];
			sumsuf[n-i-1]+=sumsuf[n-i];
		}
		sumpre[i]%=MOD;
		sumsuf[i]%=MOD;
	}
	while(m--) {
		rep(i, n) {
			dpre[i]=((i+1)*pre[n-1])%MOD;
			dsuf[i]=((n-i)*pre[n-1])%MOD;
			if(i+1<n) {
				dpre[i]-=((i+1)*suf[i+1])%MOD;
				if(dpre[i]<0) dpre[i]+=MOD;
				dsuf[i]-=sumsuf[i+1];
				if(dsuf[i]<0) dsuf[i]+=MOD;
			}
			if(i) {
				dpre[i]-=sumpre[i-1];
				if(dpre[i]<0) dpre[i]+=MOD;
				dsuf[i]-=((n-i)*pre[i-1])%MOD;
				if(dsuf[i]<0) dsuf[i]+=MOD;
			}
		}
		rep(i, n) {
			pre[i]=dpre[i];
			suf[n-i-1]=dsuf[n-i-1];
			if(i) {
				suf[n-i-1]+=suf[n-i];
				pre[i]+=pre[i-1];
			}
			suf[n-i-1]%=MOD;
			pre[i]%=MOD;
			sumpre[i]=pre[i];
			sumsuf[n-i-1]=suf[n-i-1];
			if(i) {
				sumpre[i]+=sumpre[i-1];
				sumsuf[n-i-1]+=sumsuf[n-i];
			}
			sumpre[i]%=MOD;
			sumsuf[n-i-1]%=MOD;
		}
	}
	cout << pre[n-1];
}