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
143
144
145
146
147
148
149
150
151
152
#include <iostream>

const int MAX = 1005;

using LL = unsigned long long;
using SLL = long long;

LL modInverse(SLL a, SLL m)
{
    SLL m0 = m;
    SLL y = 0, x = 1;

    if (m == 1)
      return 0;

    while (a > 1)
    {
        // q is quotient
        SLL q = a / m;
        SLL t = m;

        // m is remainder now, process same as
        // Euclid's algo
        m = a % m, a = t;
        t = y;

        // Update y and x
        y = x - q * y;
        x = t;
    }

    // Make x positive
    if (x < 0)
       x += m0;

    return x;
}

// 0 = #_#
// 1 = #_ or _#
int P[2][MAX][MAX];
int S[2][MAX][MAX];
int fac[MAX];
int ifac[MAX];
int inv[MAX];

int main()
{
    std::ios_base::sync_with_stdio(false);

    LL N,K,p;
    std::cin >> N >> K >> p;

    fac[0] = 1;
    ifac[0] = 1;
    for (int i=1;i<=N;++i)
    {
        fac[i] = LL(fac[i-1]) * i % p;
        ifac[i] = modInverse(fac[i], p);
        inv[i] = modInverse(i, p);
        // std::clog << fac[i] << " / " << ifac[i] << std::endl;
    }

    P[0][1][1] = 1;
    P[1][1][1] = 1;
    S[0][1][1] = 1;
    S[1][1][1] = 1;
    P[0][0][0] = 1;
    P[1][0][0] = 1;
    S[0][0][0] = 1;
    S[1][0][0] = 1;

    for (int k=1;k<=K;++k)
    {
        S[0][0][k] = 1;
        S[1][0][k] = 1;
        S[0][1][k] = 1;
        S[1][1][k] = 1;
    }

    for (int k=1;k<=K;++k)
    {
        //std::clog << "* " << k << std::endl;
        for (int n=2;n<N;++n)
        {
            int mn = (n+1)/2;
            LL sum0 = 0;
            LL sum1 = 0;
            if ( k <= 11 )
            for (int nn=0;nn<n;++nn)
            {
                int a = nn;
                int b = n - nn - 1;
                sum0 = ( sum0 + LL(P[0][a][k-1]) * P[0][b][k-1]
                       +   LL(P[0][a][k]) * S[0][b][k-1]
                       +   LL(S[0][a][k-1]) * P[0][b][k]) % p;
                // std::clog << n << ":" << k << " " << a << ":" << b << " \t " << sum << " :: " << f << std::endl;

                sum1 = ( sum1 + LL(S[1][a][k-1]) * P[0][b][k-1]
                    +   LL(P[1][a][k]) * S[0][b][k-1]) % p;
            }
            P[0][n][k] = sum0 * inv[n] % p;
            P[1][n][k] = sum1 * inv[n] % p;
            S[0][n][k] = (LL(S[0][n][k-1]) + P[0][n][k]) % p;
            S[1][n][k] = (LL(S[1][n][k-1]) + P[1][n][k]) % p;
        }
    }
    // for (int n=0;n<=N;++n)
    // {
    //     for (int k=0;k<=K;++k)
    //         std::clog << " \t " << P[1][n][k];
    //     std::clog << std::endl;
    // }
    // std::clog << std::endl;
    // for (int n=0;n<=N;++n)
    // {
    //     for (int k=0;k<=K;++k)
    //         std::clog << " \t " << S[1][n][k];
    //     std::clog << std::endl;
    // }
    // std::clog << std::endl;
    // for (int n=0;n<=N;++n)
    // {
    //     for (int k=0;k<=K;++k)
    //         std::clog << " \t " << P[0][n][k];
    //     std::clog << std::endl;
    // }
    // std::clog << std::endl;
    // for (int n=0;n<=N;++n)
    // {
    //     for (int k=0;k<=K;++k)
    //         std::clog << " \t " << S[0][n][k];
    //     std::clog << std::endl;
    // }
    // std::clog << std::endl;

    LL result = 0;
    for (int n=0;n<N;++n)
    {
        int a = n;
        int b = N - n - 1;
        LL sum = LL(P[1][a][K]) * S[1][b][K] % p
                      + LL(S[1][a][K-1]) * P[1][b][K] % p;
        // std::clog << N << ":" << K << " " << a << ":" << b << " \t " << sum << " :: " << f << std::endl;
        result = (result + sum) % p;
    }
    result = result * fac[N-1] % p;

    std::cout << result << std::endl;

    return 0;
}