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
67
68
69
70
#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    long long int n, m, mod;
    scanf("%lld %lld %lld\n", &n, &m, &mod);

    if (m == 1) {
        printf("%lld\n", (n*(n-1)/2) % mod);
        return 0;
    }

    long long int before [m];

    long long int thr_bef [m];
    long long int before_bef [m];

    long long int sum_right [m];

    for (long long int idx=0; idx < m; ++idx) {
        thr_bef[idx] = (m + idx*(m-idx-1))%mod;
        before[idx] = (m-idx)%mod;
        before_bef[idx] = (m-idx)%mod;
    }
    long long int prev;
    for (long long int idx=1; idx < n; ++idx) {
        prev = 0;
        for (long long int in_idx=m-1; in_idx>=0; --in_idx) {
            sum_right[in_idx] = prev;
            prev += (before_bef[in_idx]*(m-in_idx))%mod;
            prev %= mod;

        }

        for (long long int in_idx=m-1; in_idx>=0; --in_idx) {
            before_bef[in_idx] = sum_right[in_idx] + thr_bef[in_idx]*before[in_idx];
        }

        prev = 0;

        for (long long int in_idx=m-1; in_idx>=0; --in_idx) {
            prev += before_bef[m-1-in_idx] - before_bef[in_idx];
            prev %= mod;
            thr_bef[in_idx] = (prev + before_bef[in_idx]);

        }
        // pointers can do a thing :/
        for (long long int in_idx=m-1; in_idx>=0; --in_idx) {
            thr_bef[in_idx] = thr_bef[in_idx] % mod;
            before_bef[in_idx] = before_bef[in_idx] % mod;
        }

    }

    prev = 0;
    for (long long int idx=0; idx < m; ++idx) {
        prev += before_bef[idx];
        prev %= mod;
    }
    while (prev < 0) {
        prev += mod;
    }
    printf("%lld\n", prev);
    return 0;
}