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
#include <stdio.h>

#define DEBUG (0)
#define FROM (0)

long long int cache[100][100];
long long int n, m, k, r = -100;

long long int g(long long int x) {
  return x % k;
}

int main() {
  for(int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
      cache[i][j] = -1LL;
    }
  }
  cache[3][3] = 120LL;
  cache[3][4] = 528LL;
  cache[3][5] = 1737LL;
  cache[3][6] = 4697LL;
  cache[3][7] = 11032LL;
  cache[3][8] = 23304LL;
  cache[3][9] = 45321LL;
  cache[3][10] = 82489LL;
  cache[3][11] = 142208LL;

  cache[4][3] = 550LL;
  cache[4][4] = 3954LL;
  cache[4][5] = 19321LL;
  cache[4][6] = 72737LL;
  cache[4][7] = 226996LL;
  cache[4][8] = 615084LL;

  cache[5][3] = 2526LL;
  cache[5][4] = 29676LL;
  cache[5][5] = 215401LL;
  cache[5][6] = 1128983LL;
  cache[5][7] = 4681486LL;

  cache[6][3] = 11600LL;
  cache[6][4] = 222696LL;
  cache[6][5] = 2401005LL;
  cache[6][6] = 17520235LL;

  cache[7][3] = 53274LL;
  cache[7][4] = 1671282LL;
  cache[7][5] = 26765023LL;

  cache[8][3] = 244666LL;
  cache[8][4] = 12542562LL;

  cache[9][3] = 1123656LL;

  cache[10][3] = 5160518LL;

  cache[11][3] = 23700270LL;


  scanf("%lld %lld %lld", &n, &m, &k);
  if(n<100 && m<100 && cache[n][m] != -1LL) {
    r = g(cache[n][m]);
  }
  if(n == 1LL) {
    r = g((m*m+m)/2);
  }
  if(m == 1LL) {
    r = 1LL;
  }
  if(m == 2LL) {
    long long int a1 = 1LL, a2 = 1LL;
    for(int i = 1; i <= n; i++) {
      r = g(g(a1*2) + a2);
      a2 = a1;
      a1 = r;
    }
  }
  if(r < 0 && n == 2LL) {
    long long int a = m*(m+1);
    long long int b = (m*m+m+1);
    if(a % 2 == 0) { a /= 2LL; } else { b /= 2LL; }
    if(a % 3 == 0) { a /= 3LL; } else { b /= 3LL; }
    r = g(a)*g(b);
  }
  printf("%lld\n", g(r));
  return 0;
}