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
// Marcin Knapik

// Potyczki Algorytmiczne

#pragma GCC optimize "O3"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define ll long long

const int N = 1e7 + 700;

int suf[N][2];
int pref[N][2];
int suff[N];
int preff[N];
ll suma[2];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, mod;
    cin >> n >> m >> mod;

    bool bit = 0;
    suma[0] = 1;
    pref[m][0] = 1;
    suf[1][0] = 1;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            preff[j] = preff[j - 1] + pref[j][bit];
            if(preff[j] >= mod)
                preff[j] -= mod;
        }
        for(int j = m; j >= 1; j--){
            suff[j] = suff[j + 1] + suf[j][bit];
            if(suff[j] >= mod)
                suff[j] -= mod;
        }

        suma[bit ^ 1] = 0;
        for(int j = 1; j <= m; j++){
            pref[j][bit ^ 1] = (pref[j - 1][bit ^ 1] + suma[bit] - suff[j + 1] - preff[j - 1] + 1ll * (j - 1) * suf[j][bit] + mod + mod) % mod;
            suma[bit ^ 1] += pref[j][bit ^ 1];
        }
        
        for(int j = m; j >= 1; j--)
            suf[j][bit ^ 1] = (suf[j + 1][bit ^ 1] + suma[bit] - suff[j + 1] - preff[j - 1] + 1ll * (m - j) * pref[j][bit] + mod + mod) % mod;
        
        bit ^= 1;
        suma[bit] %= mod;
    } 

    cout << suma[bit] << '\n';
}