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
#include<iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long p, up, left, upleft, val;
	int n, m, x, y, curr;
	cin >> n >> m >> p;
	if(n == 1) {
		cout << (long long)m*(long long)(m+1)/2 << "\n";
		return 0;
	}
	long long dp[m][m][2];
	for(x = 0; x < m; x++) {
		for(y = 0; y < m; y++) {
			left = ((x == 0) ? 0 : dp[x-1][y][0]);
			up = ((y == 0) ? 0 : dp[x][y-1][0]);
			upleft = ((x == 0 || y == 0) ? 0 : dp[x-1][y-1][0]);
			dp[x][y][0] = ((x <= y) + left + up - upleft) % p;
		}
	}
	for(int i = 1; i < n; i++) {
		curr = (i&1);
		for(int x = 0; x < m; x++) {
			for(int y = 0; y < m; y++) {
				left = ((x == 0) ? 0 : dp[x-1][y][curr]);
				up = ((y == 0) ? 0 : dp[x][y-1][curr]);
				upleft = ((x == 0 || y == 0) ? 0 : dp[x-1][y-1][curr]);
				if(x <= y) {
					if(x == 0) {
						val = dp[y][m-1][!curr];
					}
					else {
						val = (dp[y][m-1][!curr]-dp[y][x-1][!curr])%p;
					}
				}
				else {
					val = 0;
				}
				dp[x][y][curr] = (up+left-upleft+val)%p;
			}
		}
	}
	cout << dp[m-1][m-1][curr] << "\n";
	return 0;
}