D - Race (24-11)

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
const int MOD = 10056;

int n;
int nCr[N + 5][N + 5], dp[N + 5];

void nCR() {
    for (int i = 1; i <= N; ++i) {
        nCr[i][0] = nCr[0][i] = 0;
        nCr[i][1] = i;
        nCr[i][i] = 1;
    }

    for (int i = 1; i <= N; ++i)
        for (int j = 2; j <= N; ++j)
            if (i != j)
                nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % MOD;
}

int solve(int n) {
    if(n <= 1) return 1;

    if(dp[n] != -1) return dp[n];

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int tmp = (nCr[n][i] * solve(n - i)) % MOD;
        ans = (ans + tmp) % MOD;
    }

    return dp[n] = ans;
}

int main() {
    //freopen("D-Race.inp", "r", stdin);
    //freopen("D-Race.out", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL); cout.tie(NULL);

    nCR();
    memset(dp, -1, sizeof(dp));

    int t; cin >> t;
    for(int test = 1; test <= t; ++test) {
        cin >> n;
        cout << "Case " << test << ": " << solve(n) << '\n';
    }
    return 0;
}
//dp(n) = dp(n-1) * (ToHop chap i cua n)    trong do i = 1, 2,..., n