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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    long long p;
    std::cin >> n >> m >> p;

    std::vector<long long> oneToM[2], sums[2];
    oneToM[0].resize(m, 1);
    oneToM[1].resize(m);
    sums[0].resize(m, 1);
    sums[1].resize(m, 1);

    for (int i = m - 2; i >= 0; --i) {
        sums[0][i] = sums[0][i + 1] + 1;
    }

    for (int z = 0; z < n; ++z) {
        int from = z & 1;
        int to = 1 - from;
        long long sum = oneToM[to][0] = sums[from][0];

        for (int i = 1; i < m; ++i) {
            oneToM[to][i] = (oneToM[to][i - 1] + sums[from][i]) % p;
            sum += oneToM[to][i];
            sum %= p;
        }
        sums[to][0] = sum % p;
        long long backSum = 0;
        for (int i = 1; i < m; ++i) {
            sums[to][i] = sums[to][i - 1] - oneToM[to][i - 1] + backSum + p;
            sums[to][i] %= p;
            backSum += sums[from][m - i];
            backSum %= p;
            sums[to][i] -= ((m - i) * sums[from][m - i]) % p;
            if (sums[to][i] < 0) {
                sums[to][i] += p;
            } else {
                sums[to][i] %= p;
            }
        }
    }

    std::cout << oneToM[n & 1][m - 1] << std::endl;
    return 0;
}