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 <bits/stdc++.h>
using namespace std;

#define REP(i, x) for( int i = 0; i < x; i++ )
#define FOR(i, x) for( int i = 1; i <=x; i++ )

const int MAX_N = 1010;
const int MAX_RES = 12;

int wyn_srod[MAX_RES][MAX_N];
int wyn_lew[MAX_RES][MAX_N];
int wyn_praw[MAX_RES][MAX_N];

int sum_srod[MAX_RES][MAX_N];
int sum_lew[MAX_RES][MAX_N];
int sum_praw[MAX_RES][MAX_N];
int wynik;

int silnia[MAX_N];
int odwr_siln[MAX_N];

int k, n, p;

inline int mnoz(long long a, int b){
    return (a * b) % p;
}

inline int dodaj(long long a, int b){
    return (a + b) % p;
}

inline int quick_pow(int a, int k){
    int init_a = a;
    int akt = 1;
    int wyn = 1;

    while( akt <= k ){
        if( akt & k ) wyn = mnoz(wyn, a);
        a = mnoz(a, a);
        akt <<= 1;
    }
    //cout << "LICZENIE " << init_a << " " << wyn << " " << mnoz(init_a, wyn) << endl;
    return wyn;
}

inline int odwr(int a){
    return quick_pow(a, p-2);
}

void licz_silnie(){
    int akt = 1;
    silnia[0] = 1;
    odwr_siln[0] = 1;
    FOR(i, n){
        akt = mnoz(akt, i);
        silnia[i] = akt;
        odwr_siln[i] = odwr(silnia[i]);
    }
}

inline int dwumian(int k, int n){
    return mnoz(silnia[n], mnoz(odwr_siln[k], odwr_siln[n-k]));
}

void dynamikuj(){
    wyn_srod[0][0] = 1;
    wyn_lew[0][0] = 1;
    wyn_praw[0][0] = 1;
    sum_srod[0][0] = 1;
    sum_lew[0][0] = 1;
    sum_praw[0][0] = 1;
    FOR(i, k){
        FOR(j, n){
            FOR(l, j){
                int podzial = dwumian(l-1, j-1);
                /////////////////////////////
                int srod_1 = mnoz(wyn_srod[i][l-1], sum_srod[i-1][j-l]);
                int srod_2 = mnoz(sum_srod[i-1][l-1], wyn_srod[i][j-l]);
                int razem = mnoz(wyn_srod[i-1][l-1], wyn_srod[i-1][j-l]);
                wyn_srod[i][j] = dodaj(wyn_srod[i][j], mnoz(podzial, dodaj(dodaj(srod_1, srod_2), razem)));
                /////////////////////////////
                srod_1 = mnoz(wyn_lew[i][l-1], sum_srod[i-1][j-l]);
                srod_2 = 0;
                razem = mnoz(sum_lew[i-1][l-1], wyn_srod[i-1][j-l]);
                wyn_lew[i][j] = dodaj(wyn_lew[i][j], mnoz(podzial, dodaj(dodaj(srod_1, srod_2), razem)));
                //cout <<srod_1 << " " << razem << " " << podzial << " " <<  wyn_lew[i][j] << endl;
                /////////////////////////////
                srod_1 = 0;
                srod_2 = mnoz(sum_srod[i-1][l-1], wyn_praw[i][j-l]);
                razem = mnoz(wyn_srod[i-1][l-1], sum_praw[i-1][j-l]);
                wyn_praw[i][j] = dodaj(wyn_praw[i][j], mnoz(podzial, dodaj(dodaj(srod_1, srod_2), razem)));
            }
            //cout  << i << " " << j  << " " << wyn_srod[i][j] << " " << wyn_lew[i][j] << " " << wyn_praw[i][j]  << endl;
        }
        REP(j, n+1){
            sum_srod[i][j] = dodaj(sum_srod[i-1][j], wyn_srod[i][j]);
            sum_lew[i][j] = dodaj(sum_lew[i-1][j], wyn_lew[i][j]);
            sum_praw[i][j] = dodaj(sum_praw[i-1][j], wyn_praw[i][j]);
        }
    }
    FOR(l, n){
        int podzial = dwumian(l-1, n-1);
        int wyn_1 = mnoz(sum_lew[k-1][l-1], wyn_praw[k][n-l]);
        int wyn_2 = mnoz(wyn_lew[k][l-1], sum_praw[k-1][n-l]);
        int wyn_3 = mnoz(wyn_lew[k][l-1], wyn_praw[k][n-l]);
        wynik = dodaj(wynik, mnoz(podzial, dodaj(dodaj(wyn_1, wyn_2), wyn_3)));
        //cout << wyn_1 << " " << wyn_2 << " " << wyn_3 << " " << l << " " << wynik << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> p;
    licz_silnie();
    if( k >= 11 ) {
        cout << 0 << endl;
        return 0;
    }
    dynamikuj();
    cout << wynik << endl;
    return 0;
}