1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>

#define M 10000000

int t[M], r[M];

int main ()
{
  int n, m, p;
  scanf ("%i%i%i", &n, &m, &p);
  t[m-1] = 1;
  while (n--)
  {
    int s = 0;
    for (int i=0; i<m; i++) r[i] = (i+1LL) * (t[m-1] + p - (m-i-2>=0? t[m-i-2]: 0))%p + p - s, s = (s + t[i])%p;
    for (int i=0; i<m; i++) t[i] = (r[i] + (i-1>=0? t[i-1]: 0))%p;
  }
  printf ("%i\n", t[m-1]);
  return 0;
}