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

using namespace std;

long long n = 6, m = 9,  p = 813443923;

long long Max(long long x, long long y) {
    return (x >= y) ? x : y;
}

long long Min(long long x, long long y) {
    return (x <= y) ? x : y;
}

map <pair< long long, pair< long long, long long > >, long long> plot;

long long findPath(long long sztacheta, long long seg_from, long long seg_to) {
    long long sum = 0;

    long long d = seg_to - seg_from + 1;
    if (sztacheta == n - 1) {
        if (plot.find(make_pair(sztacheta, make_pair(seg_from, seg_to))) != plot.end()) {
            return plot[make_pair(sztacheta, make_pair(seg_from, seg_to))];
        }
        if (plot.find(make_pair(sztacheta, make_pair(m - 1 - seg_to, m - 1 - seg_from))) != plot.end()) {
            return plot[make_pair(sztacheta, make_pair(m - 1 - seg_to, m - 1 - seg_from))];
        }
        sum = (seg_from + 1) * (m - seg_from);
        if (seg_from < seg_to) {
            long long x = m - seg_from - 1;
            long long y = m - seg_to;
            long long l = x - y + 1;
            sum += ((x + y) * l / 2);
        }
        sum %= p;
        plot[make_pair(sztacheta, make_pair(seg_from, seg_to))] = sum;
        return sum;
    }

    if (plot.find(make_pair(sztacheta,make_pair(seg_from,seg_to))) != plot.end()) {
        return plot[make_pair(sztacheta, make_pair(seg_from, seg_to))];
    }
    if (plot.find(make_pair(sztacheta, make_pair(m - 1 - seg_to, m - 1 - seg_from))) != plot.end()) {
        return plot[make_pair(sztacheta, make_pair(m - 1 - seg_to, m - 1 - seg_from))];
    }

    for (long long i = 0; i <= seg_to; i++) {
        for (long long j = Max(i, seg_from); j <= m - 1; j++) {
            sum+=findPath(sztacheta+1,i,j);
            sum %= p;
        }
    }
    sum %= p;
    plot[make_pair(sztacheta, make_pair(seg_from, seg_to))] = sum;
    return sum;
}


int main()
{ 
    cin >> n >> m >> p;

    long long suma = 0;
    suma += findPath(0, 0, m - 1);

    cout << suma % p << endl;

    return 0;
}