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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)


using namespace std;
ll INF = LONG_LONG_MAX;

template <typename T, typename L>
void read(vector<T> & _data, L & _size, bool _shift) {
    _data.resize(_size + (ll)_shift);
    for (ll i = (ll)_shift; i < _size + (ll)_shift; i++)
        cin >> _data[i];
}

template <typename T, typename L>
void read(vector<vector<T>> & _data, L & _rows, L & _cols, bool _shiftRows, bool _shiftCols) {
    _data.resize(_rows + (ll)_shiftRows);
    for (ll i = 0; i < _rows + (ll)_shiftRows; i++)
        _data[i].resize(_cols + (ll)_shiftCols);
    for (ll i = (ll)_shiftRows; i < _rows + (ll)_shiftRows; i++)
        for (ll j = (ll)_shiftCols; j < _cols + (ll)_shiftCols; j++)
            cin >> _data[i][j];
}

template <typename T>
void write(vector<T> & _data, bool _shift) {
    for (ll i = (ll)_shift; i < _data.size(); i++)
        cout << _data[i] << " ";
    cout << endl;
}


//TODO: SOLUTION


void solve() {
    ll n, m, p; cin >> n >> m >> p;
    vvll dp(n, vll(m, 0)); // dp[i][j] = kolorowania, t.że sztacheta i ma j pokolorowany najwyżej
    vvll presums(n, vll(m, 0));

    dp[0][0] = 1;
    presums[0][0] = 1;

    for (ll j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + 1;
        dp[0][j] = dp[0][j] % p;
        presums[0][j] = dp[0][j] + presums[0][j-1];
        presums[0][j] = presums[0][j] % p;
    }

    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i-1][m-1]; // symetria
        presums[i][0] = dp[i][0];

        for (int j = 1; j < m; j++) {
            dp[i][j] = dp[i][j - 1]; // jestesmy polaczeni od lewej ponizej j
            dp[i][j] += j * dp[i-1][m-j-1]; // mamy spod i jestesmy polaczeni powyzej j-1 (symetria)
            dp[i][j] = dp[i][j] % p;

            // case gdy i,j jest jedyny pomalowany
            ll powy = presums[i-1][m-1] - presums[i-1][j-1]; // koncza sie powyzej j
            while (powy < 0)
                powy += p;

            ll poni;
            if (j == m-1)
                poni = 0;
            else
                poni = presums[i-1][m-j-2];

            ll sposy = powy - poni;
            while (sposy < 0)
                sposy += p;

            dp[i][j] += sposy;
            dp[i][j] = dp[i][j] % p;

            presums[i][j] = presums[i][j-1] + dp[i][j];
            presums[i][j] = presums[i][j] % p;
        }
    }

    cout << presums[n-1][m-1] << endl;
}


int main() {
    ios::sync_with_stdio(false);
    // TODO: Set value of this variable manually
    bool _multipleTestCases = false;

    if (_multipleTestCases) {
        ll t; cin >> t;
        while (t--)
            solve();
    }
    else {
        solve();
    }

    return 0;
}