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
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
#include <set>
#include <algorithm>
#include <deque>
#include <map>
#include<bits/stdc++.h> 
using namespace std;

int const MAXN = 1001;
int const MAXK = 11;
long N, K;
long long P;
long long result;
long long EH[MAXN][MAXK];
long long SH[MAXN][MAXK];
long long EM[MAXN][MAXK];
long long SM[MAXN][MAXK];
long long B[MAXN][MAXN];
long long tmp;
long MIN_N[] = {1, 2, 3, 5, 9, 17, 33, 65, 129, 257, 513} ;

long long modmult(long long x, long long y) {
  return (x*y) % P;
}

void initB() {
  B[0][0] = 1;
  B[1][0] = 1;
  B[1][1] = 1;
  for (int n=2; n<=N; n++) {
    B[n][0] = 1;
    for(int k=1; k<=n; k++) {
      B[n][k] = (B[n-1][k] + B[n-1][k-1]) % P;
    }
  }
}


void init() {
  EH[1][1] = 0;
  EH[1][1] = 1;
  SH[1][0] = 0;
  SH[1][1] = 0;
  SH[1][2] = 1;
  EM[1][0] = 0;
  EM[1][1] = 1;
  SM[1][0] = 0;
  SM[1][1] = 0;
  SM[1][2] = 1; 
  for (int k=3; k<=K; k++) {
    SH[1][k] = 1;
    SM[1][k] = 1;
  }
}

long long compute_result_i(int i){
    tmp = (modmult(EM[i][K], EM[N-1-i][K]) + 
          modmult(EM[i][K], SM[N-1-i][K]) + 
          modmult(SM[i][K], EM[N-1-i][K])) % P;
    return modmult(B[N-1][i], tmp);
}

long long compute_eh_i(int n, int k, int i){
  tmp = (modmult(EH[i][k], EH[n-1-i][k-1]) + 
        modmult(EH[i][k-1], EH[n-1-i][k]) +
        modmult(EH[i][k-1], EH[n-1-i][k-1]) +
        modmult(EH[i][k], SH[n-1-i][k-1]) +
        modmult(SH[i][k-1], EH[n-1-i][k])) % P;
  return modmult( B[n-1][i], tmp);
}

long long compute_em_i(int n, int k, int i){
  tmp = (modmult(EM[i][k], EH[n-1-i][k-1]) +
         modmult(EM[i][k], SH[n-1-i][k-1]) +
         modmult(SM[i][k], EH[n-1-i][k-1])) % P;
  return modmult(B[n-1][i], tmp);
}

void solve() {
  if (K > 10 || N < MIN_N[K]) {
    return;
  }
  for (int n=2; n < N; n++) {
    for (int k=1; k <= K; k++) {
      EH[n][k] = (EH[n][k] + 2*EH[n-1][k]) % P;
      EM[n][k] = (EM[n][k] + EH[n-1][k-1] + EM[n-1][k]) % P;

      for (int i=1; i<n/2; i++) {
        EH[n][k] = (EH[n][k] + 2*compute_eh_i(n,k,i)) % P;        
      }
      if (n % 2 == 1) {
        EH[n][k] = (EH[n][k] + compute_eh_i(n,k,n / 2)) % P;                
      }
      for (int i=1; i<n-1; i++) {
        EM[n][k] = (EM[n][k] + compute_em_i(n,k,i)) % P; 
      }
      SH[n][k] = (SH[n][k-1] + EH[n][k-1]) % P;
      SM[n][k] = (SM[n][k-1] + EM[n][k-1]) % P;
    }
  }
  result = (result + 2 * EM[N-1][K]) % P; // side selected
  for (int i = 1; i < N/2; i++) {
    result = (result + 2 *compute_result_i(i)) % P;
  }
  if (N % 2 == 1){
    result = (result + compute_result_i(N / 2)) % P;    
  }
  return;
}

int main() {
  scanf("%ld %ld %lld\n", &N, &K, &P);
  initB();
  init();
  solve();
  printf("%lld\n", result);
  return 0;
}