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
59
60
61
62
63
64
65
66
#include <cstdlib>
#include <cstdint>

#include <iostream>
#include <vector>

int main() {
    uint64_t n, m, p;
    std::cin >> n >> m >> p;

    std::vector<uint64_t> prev_prefixes, curr_prefixes;
    std::vector<uint64_t> prev_totals, curr_totals;
    prev_prefixes.resize(m + 1, 0);
    curr_prefixes.reserve(m + 1);
    prev_totals.resize(m + 1, 0);
    curr_totals.reserve(m + 1);

    // Prepare the first slice
    uint64_t acc = 0;
    curr_prefixes.push_back(0);
    curr_totals.push_back(0);

    for (uint64_t i = 1; i <= m; i++) {
        curr_prefixes.push_back(i % p);
        acc = (acc + i) % p;
        curr_totals.push_back(acc);
    }

    --n;

    while (n --> 0) {
        std::swap(prev_prefixes, curr_prefixes);
        std::swap(prev_totals, curr_totals);
        acc = 0;

        for (uint64_t i = 1; i <= m; i++) {
            uint64_t my_count = 0;

            // All configurations from the previous length can be applied here as well
            // because we can just extend a segment in the current layer
            my_count += curr_prefixes[i - 1]; 

            my_count += (i - 1) * prev_prefixes[m - i + 1];

            // We need to add segments which overlap with the 1-segment
            uint64_t one_seg = 0;

            // Add all previous combinations
            one_seg += prev_totals[m];

            // Remove all combinations which do not touch from the left or right side
            one_seg += p - prev_totals[i - 1];
            one_seg += p - prev_totals[m - i];

            my_count += one_seg;

            my_count = my_count % p;

            curr_prefixes[i] = my_count;
            curr_totals[i] = (curr_totals[i - 1] + my_count) % p;
        }
    }

    std::cout << curr_totals[m] << std::endl;
    return 0;
}