Cricinfo

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define Mod 10000007
#define M 10
#define Max 10001

int runs[] = {0, 1, 2, 3, 4, 6, 1, 2, 3, 5, 1, 2, 5, 7, 0};
int N, n, depth, ans, extra[] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0};
int dp[M][Max];

int solve(int indx, int sum) {
    if(indx == depth)
        return 1;
    if(sum <= 0)
        return 1;

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

    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = (ans % Mod + solve(indx + 1 - extra[i], sum - runs[i]) % Mod) % Mod;

    return dp[indx][sum] = (ans + 1) %  Mod;
}


int main() {
    depth = 6, n = sizeof(runs) / sizeof(runs[0]);
    int tcase, caseNo = 0;
    scanf("%d", &tcase);
    memset(dp, -1, sizeof dp);
    while (tcase--) {
        scanf("%d", &N);
        printf("Case %d: %d\n", ++caseNo, solve(0, N));
    }
    return 0;
}