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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>

bool testOverlap(int x1, int x2, int y1, int y2) {
    return (x1 >= y1 && x1 <= y2) ||
           (x2 >= y1 && x2 <= y2) ||
           (y1 >= x1 && y1 <= x2) ||
           (y2 >= x1 && y2 <= x2);
}

int brute(int n, int m, int p, int l, int szt) {
    int res = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j + i <= m; j++) {
            if (szt < n && testOverlap(p, p + l - 1, j, j + i - 1)) {
                res += brute(n, m, j, i, szt + 1);
            }
            if (szt == n && testOverlap(p, p + l - 1, j, j + i - 1)) {
                res += 1;
            }
        }
    }
    return res;
}

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;
    /*for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 3; j++) {
            std::cout << brute(j, i, 0, i, 1) << " ";
        }
        std::cout << "\n";
    }*/

    if (m == 1) {
        std::cout << 1 % k;
        return 0;
    }

    if (m == 2) {
        long long int res = 0;
        long long int a, b;
        if (n == 1) {
            std::cout << 3 % k;
            return 0;
        }
        if (n == 2) {
            std::cout << 7 % k;
            return 0;
        }
        a = 3;
        b = 7;
        for (int i = 2; i < n; i++) {
            res = 2LL * b + a;
            a = b;
            b = res % k;
        }
        std::cout << res % k;
        return 0;
    }

    if (n == 1) {
        long long int res = 1;
        for (int i = 1; i < m; i++) {
            res = (res + 1 + i) % k;
        }
        std::cout << res % k;
        return 0;
    }

    if (n == 2) {
        long long int a, b, c, res;
        a = 1;
        b = 7;
        c = 26;
        if (m == 3) {
            std::cout << 26 % k;
            return 0;
        }
        for (long long int i = 3; i < m; i++) {
            res = 3LL * c - 3LL * b + a + 4LL * (i);
            a = b;
            b = c;
            c = res % k;
        }
        std::cout << res % k;
        return 0;
    }

    std::cout<<brute(n, m, 0, m, 1) % k;

    return 0;
}