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
#include <iostream>
#define U unsigned long long

U N, M, P, ind, a = 0;
U *matrixR, *matrixL, *matrixSquashed0, *matrixSquashed1;

void init() {
    matrixR = new U[M];
    matrixL = new U[M];
    matrixSquashed0 = new U[M];
    matrixSquashed1 = new U[M];
    for (auto j = a; j < M; ++j)
    {
        matrixSquashed0[j] = 1;
        matrixSquashed1[j] = 1;
        matrixR[j] = 1;
        matrixL[j] = 0;
    }
    while (--ind >= 1) matrixSquashed0[ind - 1] = matrixSquashed0[ind] + 1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin >> N;
    std::cin >> M;
    ind = M;
    std::cin >> P;
    init();
    for (U z = 0; z < N; ++z)
    {
        a = 0;
        auto *matrixSquashedFrom = z % 2 ? matrixSquashed1 : matrixSquashed0;
        auto *matrixSquashedTo = z % 2 ? matrixSquashed0 : matrixSquashed1;
        auto *matrixTo = z % 2 ? matrixL : matrixR;
        matrixTo[0] = matrixSquashedFrom[0];
        auto sum = matrixTo[0];
        for (auto ind = 1; ind < M; ++ind)
        {
            matrixTo[ind] = (matrixTo[ind - 1] + matrixSquashedFrom[ind]) % P;
            sum = (sum + matrixTo[ind]) % P;
        }
        matrixSquashedTo[a] = sum % P;
        for (auto ind = a + 1; ind < M; ++ind)
        {
            matrixSquashedTo[ind] = (matrixSquashedTo[ind - 1] + (P - (matrixTo[ind - 1] % P)) + a) % P;
            auto symmetric_ind = M - ind;
            a = (a + matrixSquashedFrom[symmetric_ind]) % P;
            matrixSquashedTo[ind] = (matrixSquashedTo[ind] + (P - ((symmetric_ind * matrixSquashedFrom[symmetric_ind]) % P))) % P;
        }
    }
    auto ans = N % 2 == 1 ? matrixR[M - 1] : matrixL[M - 1];
    std::cout << ans << std::endl;
    return 0;
}