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

using namespace std;

typedef long long ll;

const int M = 10000010;
ll T[M][2], PS[M][2];

int main() {
    int n,m,p; 
    
    scanf("%d%d%d",&n, &m, &p);
   
    for (int i = 1; i <= m; i++) {
        T[i][0] = T[i-1][0]+1;
        PS[i][0] = PS[i-1][0] + T[i][0];
        PS[i][0] %= p;
    }
    int w = 1;
    for (int i=0;i<n-1;i++) {
        PS[1][w] = T[1][w] = T[m][1-w];
        for (int j=2;j<=m;j++) {
            T[j][w] = T[j-1][w];
            T[j][w] += T[m-j+1][1-w]*(j-1);
            T[j][w] %= p;
            T[j][w] += p + p + PS[m][1-w]-PS[j-1][1-w]-PS[m-j][1-w];
            T[j][w] %= p;
            PS[j][w] = PS[j-1][w]+T[j][w];
            PS[j][w] %= p;
            
        }
        w = 1-w;
    }
    
    printf("%lld\n",PS[m][1-w]);
    return 0;
 
}