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
#define _CRT_SECURE_NO_WARNINGS
#define ONLINE_JUDGE
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
typedef long long LL;

class Solver
{
public:
    int solve(LL rails, LL segments, LL prime)
    {
        if (segments == 1)
            return 1;

        this->rails = rails;
        this->segments = segments;
        this->prime = prime;

        paintings = vector<vector<LL>>(rails + 1, vector<LL>(segments + 1, 0));
        fillForFirstRail();

        FOR(rail, 2, rails)
        {
            paintings[rail][1] = paintings[rail - 1][segments] + (prime - paintings[rail - 1][segments - 1]);
            paintings[rail][1] %= prime;
            vector<LL> sumOfPaintingsOfPreviousRailUpToIndex(segments + 1, 0);
            FOR(k, 1, segments)
            {
                sumOfPaintingsOfPreviousRailUpToIndex[k] = sumOfPaintingsOfPreviousRailUpToIndex[k - 1];
                sumOfPaintingsOfPreviousRailUpToIndex[k] += (prime - paintings[rail - 1][k - 1]);
                sumOfPaintingsOfPreviousRailUpToIndex[k] %= prime;
            }

            FOR(segment, 2, segments)
            {
                paintings[rail][segment] = paintings[rail][segment - 1];
                paintings[rail][segment] += paintings[rail - 1][segments] * segment;
                paintings[rail][segment] %= prime;

                paintings[rail][segment] += (prime - paintings[rail - 1][segments - segment]) * segment;
                paintings[rail][segment] %= prime;

                paintings[rail][segment] += sumOfPaintingsOfPreviousRailUpToIndex[segment];
                paintings[rail][segment] %= prime;
            }
        }

        return paintings[rails][segments];
}
private:

    void fillForFirstRail()
    {
        for (int segment = 1; segment <= segments; ++segment)
            paintings[1][segment] = (paintings[1][segment - 1] + segment % prime);
    }

    vector<vector<LL>> paintings;
    LL rails;
    LL segments;
    LL prime;
};

int main()
{
    Solver solver;
#ifndef ONLINE_JUDGE
    const int randomPrime = 100000007;
    assert(solver.solve(1, 1, randomPrime) == 1);
    for (int rails = 2; rails <= 100; ++rails)
        assert(solver.solve(rails, 1, randomPrime) == 1);

    assert(solver.solve(1, 2, randomPrime) == 3);
    assert(solver.solve(1, 3, randomPrime) == 6);
    assert(solver.solve(1, 4, randomPrime) == 10);
    assert(solver.solve(1, 5, randomPrime) == 15);
    assert(solver.solve(3, 2, randomPrime) == 17);
    assert(solver.solve(6, 9, 813443923) == 57);
    printf("Tests finished.\n");
#endif
    int rails, segments, prime;
    scanf("%d %d %d", &rails, &segments, &prime);
    printf("%d\n", solver.solve(rails, segments, prime));
#ifndef ONLINE_JUDGE
    system("pause");
#endif
    return 0;
}