1326 - Race

#include<bits/stdc++.h>
using namespace std;
#define mx 1005
#define mod 10056
int dp[mx][mx],result[mx];
 
void calculate()
{
    int i,j;
    dp[1][1] = 1;
    dp[2][1] = 1;
    dp[2][2] = 2;
    for(i=3; i<mx; i++)
    {
        dp[i][1] = 1;
        for(j=2; j<i; j++)
            dp[i][j] = ((dp[i-1][j]+dp[i-1][j-1])*j)%mod;
        dp[i][i] = ((dp[i-1][j-1])*i)%mod;
    }
 
    for(i=1; i<mx; i++)
    {
        result[i] = 0;
        for(j=1; j<=i; j++)
            result[i] = (result[i] + dp[i][j])%mod;
    }
}
 
 
int main()
{
    int T,n,c=1;
    calculate();
    cin >> T;
    while(T--)
    {
        cin >> n;
        cout << "Case " << c++ << ": " << result[n] << endl;
    }
    return 0;
}