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
#include <cstdio>
#include <set>
#include <map>
#include <utility>
#include <deque>

int n,m;
long p;
long result = 0;
long** A[2];
long* B;
long* C;
int i_curr = 0;
int i_next = 1;

void read() {
  scanf("%d %d %ld\n", &n, &m, &p);
  for (int k=0; k<2; k++) {
    A[k] = new long *[m];
    for(int i=0; i<m; i++) {
      A[k][i] = new long[m];
    }
  }
  for (int i=0; i<m; i++) {
    for (int j=i; j<m; j++) {
      A[i_curr][i][j] = 1;
      A[i_next][i][j] = 0;
    }
  }
  B = new long[m];
  C = new long[m];
}

void print(int s) {
  for (int i=0; i<m; i++) {
    for (int j=i; j<m; j++) {
      printf("*s=%d - A[%d](%d,%d)=%ld\n", s, i_curr, i, j, A[i_curr][i][j]);
    }
  }
}

int main() {
  read();
 // print(0);
  for (int s=0; s<n-1; s++) {
 //   printf("%d\n", s);
    for (int i=0; i<m; i++) {
      B[i] = 0;
      for (int j=i; j<m; j++) {
        B[i] = (B[i] + A[i_curr][i][j]) % p;
      }
    }
    for (int i=0; i<m; i++) {
      C[i] = 0;
      for (int ix=0; ix < i; ix ++) {
        for (int jx = i; jx < m; jx++) {
          C[i] = (C[i] + A[i_curr][ix][jx]) % p;
        }
      }
    }//
    for (int i=0; i<m; i++) {
      for (int j=i; j<m; j++) {
        A[i_next][i][j] = (A[i_next][i][j] + C[i]) % p;
      }
      for (int j=i; j<m; j++) {
        for (int ix=i; ix <= j; ix ++) {
          A[i_next][i][j] = (A[i_next][i][j] + B[ix]) % p;
        }
      }
    }
    for (int i=0; i<m; i++) {
      for (int j=i; j<m; j++) {
        A[i_curr][i][j] = 0;
      }
    }
    if (i_curr == 0) {
      i_curr = 1;
      i_next = 0;
    } else {
      i_curr = 0;
      i_next = 1;
    }
 //   print(s+1);
  }
  
  for (int i=0; i<m; i++) {
    for (int j=i; j<m; j++) {
      result = (result + A[i_curr][i][j]) % p;
    }
  }

  printf("%ld\n", result);
  return 0;
}