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
#include <iostream>
#include <vector>
using namespace std;

long long n, m, p;

vector<vector<int>> dp;
vector<vector<int>> prefsum;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> p;
	dp.resize(n);
	prefsum.resize(n);
	for(int i = 0; i < n; i++) dp[i].resize(m), prefsum[i].resize(m);
	for(int i = 0; i < m; i++) dp[0][i] = i + 1;
	prefsum[0][0] = 1;
	for(int i = 1; i < m; i++) prefsum[0][i] = prefsum[0][i - 1] + dp[0][i];

	for(int k = 1; k < n; k++){
		long long dg = 0;
		for(long long i = 0; i < m; i++){
			long long base = (i + 1) * (prefsum[k - 1][m - 1]) - (i + 1) * (i == m - 1 ? 0 : prefsum[k - 1][m - 2 - i]); base %= p;
			dp[k][i] = (base - dg + p) % p;
			dg = (dg + prefsum[k - 1][i]) % p;
		}
		prefsum[k][0] = dp[k][0];
		for(long long i = 1; i < m; i++) prefsum[k][i] = (prefsum[k][i - 1] + dp[k][i]) % p;
	}
	cout << prefsum[n - 1][m - 1] << "\n";
}