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
#include <bits/stdc++.h>
#define REP(i,n) for(int _n=(n), i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define TRACE(x) cerr << "TRACE(" #x ")" << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << endl;
typedef long long LL; typedef unsigned long long ULL;

void init_io() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

unsigned MOD;

class Mod {
public:
  Mod(unsigned x=0):v(x) {}
  static Mod reduce(ULL x) { return Mod(x % MOD); }
  unsigned get() const { return v; }
  Mod operator+(Mod b) const {
    unsigned res = v+b.v;
    if (res >= MOD) res -= MOD;
    return res;
  }
  void operator+=(Mod b) { *this = *this + b; }
  Mod operator-(Mod b) const { return *this + Mod(MOD-b.v); }
  void operator-=(Mod b) { *this = *this - b; }
  Mod operator*(Mod b) const { return reduce(ULL(v) * ULL(b.v)); }
  void operator*=(Mod b) { *this = *this * b; }

  friend Mod operator+(unsigned a, Mod b) { return Mod(a) + b; }
  friend Mod operator-(unsigned a, Mod b) { return Mod(a) - b; }
  friend Mod operator*(unsigned a, Mod b) { return Mod(a) * b; }
private:
  unsigned v;
};

Mod solve(unsigned sx, unsigned sy) {
  // f[y] = use only top y rows
  std::vector<Mod> f(sy+1, 0);
  f[sy] = 1;
  std::vector<Mod> f_next(sy+1, 0);
  std::vector<Mod> f_prefix(sy+2, 0);
  std::vector<Mod> f_weighted_prefix(sy+2, 0);

  REP(x, sx) {
    // f_prefix[y] = f[0] + ... + f[y-1], 0 <= y <= sy+1
    f_prefix[0] = 0;
    FOR(y, 0, sy) f_prefix[y+1] = f_prefix[y] + f[y];

    // f_weighted_prefix[y] = 0 f[0] + 1 f[1] + ... (y-1) f[y-1], 0 <= y <= sy+1
    f_weighted_prefix[0] = 0;
    FOR(y, 0, sy) f_weighted_prefix[y+1] = f_weighted_prefix[y] + y * f[y];

    FOR(y, 0, sy) {
      f_next[y] =
        Mod::reduce(ULL(y)*(y+1) / 2) * f[sy]
        - y * f_prefix[y+1]
        + f_weighted_prefix[y+1]
        - sy * (f_prefix[sy+1] - f_prefix[sy-y])
        + (f_weighted_prefix[sy+1] - f_weighted_prefix[sy-y]);
    }
    f.swap(f_next);
  }
  return f[sy];
}

int main() {
  init_io();

  unsigned sx, sy;
  std::cin >> sx >> sy >> MOD;
  auto result = solve(sx, sy);
  std::cout << result.get() << "\n";
}