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 #include using namespace std; const int N = 1007; const int K = 11; int mod; int n, k; int Newton[N][N]; int dp[N][K][3]; int pref[N][K][3]; void add(int &a, int v){ a += v; if(a >= mod) a -= mod; } int main(){ scanf("%d %d %d", &n, &k, &mod); if(k >= K){ puts("0"); return 0; } for(int i = 0; i <= n; ++i){ Newton[i][0] = Newton[i][i] = 1; for(int j = 1; j < i; ++j) Newton[i][j] = (Newton[i - 1][j - 1] + Newton[i - 1][j])%mod; } dp[1][0][0] = 1; dp[2][1][0] = 2; dp[1][0][1] = 1; dp[2][0][1] = 1; dp[2][1][1] = 1; dp[1][0][2] = 1; dp[2][0][2] = 2; for(int i = 1; i <= 2; ++i) for(int t = 0; t < 3; ++t){ pref[i][0][t] = dp[i][0][t]; for(int j = 1; j <= k; ++j) pref[i][j][t] = pref[i][j - 1][t] + dp[i][j][t]; } for(int i = 3; i <= n; ++i){ pref[i][0][0] = dp[i][0][0] = 0; pref[i][0][1] = dp[i][0][1] = 1; pref[i][0][2] = dp[i][0][2] = (2LL * dp[i - 1][0][2])%mod; for(int j = 1; j <= k; ++j){ add(dp[i][j][0], (2LL * dp[i - 1][j - 1][1])%mod); add(dp[i][j][1], dp[i - 1][j][1]); add(dp[i][j][1], dp[i - 1][j - 1][2]); add(dp[i][j][2], (2LL * dp[i - 1][j][2])%mod); for(int mid = 2; mid < i; ++mid){ add(dp[i][j][0], (((1LL * dp[mid - 1][j - 1][1] * pref[i - mid][j - 1][1])%mod) * Newton[i - 1][mid - 1])%mod); if(j > 1) add(dp[i][j][0], (((1LL * pref[mid - 1][j - 2][1] * dp[i - mid][j - 1][1])%mod) * Newton[i - 1][mid - 1])%mod); add(dp[i][j][1], (((1LL * dp[mid - 1][j - 1][2] * pref[i - mid][j][1])%mod) * Newton[i - 1][mid - 1])%mod); if(j > 1) add(dp[i][j][1], (((1LL * pref[mid - 1][j - 2][2] * dp[i - mid][j][1])%mod) * Newton[i - 1][mid - 1])%mod); add(dp[i][j][2], (((1LL * dp[mid - 1][j - 1][2] * dp[i - mid][j - 1][2])%mod) * Newton[i - 1][mid - 1])%mod); add(dp[i][j][2], (((1LL * dp[mid - 1][j][2] * pref[i - mid][j - 1][2])%mod) * Newton[i - 1][mid - 1])%mod); add(dp[i][j][2], (((1LL * pref[mid - 1][j - 1][2] * dp[i - mid][j][2])%mod) * Newton[i - 1][mid - 1])%mod); } pref[i][j][0] = (pref[i][j - 1][0] + dp[i][j][0])%mod; pref[i][j][1] = (pref[i][j - 1][1] + dp[i][j][1])%mod; pref[i][j][2] = (pref[i][j - 1][2] + dp[i][j][2])%mod; } } printf("%d\n", dp[n][k][0]); return 0; }