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

using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
	long long n, m, mod; cin>>n>>m>>mod;
	
	vector<vector<long long>> tab(2, vector<long long>(m, 1));

	for(long long i = 0; i <= n; i++){
		long long cur = i%2;
		long long nxt = cur^1;
		
		long long sum = 0;
		for(long long j = 0; j < m; j++){
			sum+=tab[cur][j];	
		}
		sum%=mod;
		long long offset = 0;
		tab[nxt][m-1] = sum;
		for(long long j = 0; j < m-1; j++){
			sum = (mod+sum-tab[cur][m-1-j])%mod;	
			offset+=tab[cur][j]-tab[cur][j+1];
			offset%=mod;
			tab[nxt][m-2-j] = (mod+tab[nxt][m-1-j]+sum-((m-1-j)*(offset))%mod)%mod;
		}
	}
	cout<<tab[n%2][0]<<'\n';
	return 0;
}