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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <cstdio>

typedef long long LL;

int p;

inline int pmul(int a, int b) {
  return (LL(a)*b) % p;
}

int main() {
  int n, k; scanf("%d %d %d", &n, &k, &p);

  int** newton = new int*[n+1];
  for (int i=0; i<=n; ++i) {
    newton[i] = new int[i+1];
    newton[i][0] = 1;
    newton[i][i] = 1;
    for (int j=1; j<i; ++j) {
      newton[i][j] = (newton[i-1][j-1] + newton[i-1][j]) % p;
    }
  }
/*
  printf("Newton\n");
  for (int i=0; i<=n; ++i) {
    for (int j=0; j<=i; ++j) {
      printf("%d ", newton[i][j]);
    }
    printf("\n");
  }
*/
  int* fact = new int[n+1];
  fact[0] = 1;
  for (int i=1; i<=n; ++i) {
    fact[i] = (LL(fact[i-1])*i) % p;
  }
/*  
  printf("Factorial\n");
  for (int i=0; i<=n; ++i) {
    printf("%d ", fact[i]);
  }
  printf("\n");
*/
  int** two_side = new int*[k+1];
  int** one_side = new int*[k+1];
  int** two_side_agg = new int*[k+1];
  int** one_side_agg = new int*[k+1];
  for (int i=0; i<=k; ++i) {
    two_side[i] = new int[n+1];
    one_side[i] = new int[n+1];
    two_side_agg[i] = new int[n+1];
    one_side_agg[i] = new int[n+1];
  }

  two_side[0][0] = 1;
  two_side_agg[0][0] = 1;
  for (int i=1; i<=n; ++i) {
    two_side[0][i] = 0;
    two_side_agg[0][i] = 0;
  }


  for (int l=1; l<=k; ++l) {
    two_side[l][0] = 0;
    two_side_agg[l][0] = two_side_agg[l-1][0];
    for (int i=1; i<=n; ++i) {
      if (l == 1 && i == 1) {
        two_side[l][i] = 1;
        two_side_agg[l][i] = (two_side_agg[l-1][i] + 1) % p;
        continue;
      }
      LL sum = 0;
      for (int j=0; j<i; ++j) {
        sum += pmul(newton[i-1][j],
            ((pmul(two_side[l][j], two_side_agg[l-1][i-j-1]) +
              pmul(two_side[l][i-j-1], two_side_agg[l-1][j])) % p +
              pmul(two_side[l-1][j], two_side[l-1][i-j-1])) % p);
      }
      two_side[l][i] = (int)(sum % p);
      two_side_agg[l][i] = (two_side_agg[l-1][i] + two_side[l][i]) % p;;
    }
  }
/*
  printf("Two side\n");
  for (int l=0; l<=k; ++l) {
    for (int i=0; i<=n; ++i) {
      printf("%d ", two_side[l][i]);
    }
    printf("\n");
  }
*/
  one_side[0][0] = 1;
  one_side_agg[0][0] = 1;
  for (int i=1; i<=n; ++i) {
    one_side[0][i] = 0;
    one_side_agg[0][i] = 0;
  }

  for (int l=1; l<=k; ++l) {
    one_side[l][0] = 0;
    one_side_agg[l][0] = one_side_agg[l-1][0];
      for (int i=1; i<=n; ++i) {
      if (l == 1 && i == 1) {
        one_side[l][i] = 1;
        one_side_agg[l][i] = (one_side_agg[l-1][i] + 1) % p;
        continue;
      }
      LL sum = 0;
      for (int j=0; j<i; ++j) {
        sum += pmul(newton[i-1][j],
            ((pmul(one_side[l][j], two_side_agg[l-1][i-j-1]) +
              pmul(two_side[l-1][i-j-1], one_side_agg[l][j])) % p +
              p - pmul(one_side[l][j], two_side[l-1][i-j-1])) % p);
      }
      one_side[l][i] = (int)(sum % p);
      one_side_agg[l][i] = (one_side_agg[l-1][i] + one_side[l][i]) % p;
    }
  }
/*
  printf("One side\n");
  for (int l=0; l<=k; ++l) {
    for (int i=0; i<=n; ++i) {
      printf("%d ", one_side[l][i]);
    }
    printf("\n");
  }
*/
  LL result = 0;
  if (n == 1) {
    result = 1;
  } else { 
    for (int j=0; j<n; ++j) {
      result += pmul(newton[n-1][j],
          ((pmul(one_side[k][j], one_side_agg[k-1][n-j-1]) +
            pmul(one_side[k][n-j-1], one_side_agg[k-1][j])) % p +
            pmul(one_side[k][j], one_side[k][n-j-1])) % p);
    }
  }

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