牛牛铺地毯

import java.util.Scanner;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] nums = new int[N];
        for(int i =0; i<N; i++){
            nums[i] = in.nextInt();
        }
        long[] res = new long[N];
        for(int i = 0; i< N ; i++){
            res[i] = calculate(nums[i]);
        }
        for(int i =0; i< N ;i++){
            System.out.println(res[i]);
        }


    }
//动态规划
    public static long calculate(int K){
        long[] dp = new long[K+1];

        for(int i = 1; i<= K ;i++){
            if(i==1) dp[i] = 1;
            else if(i == 2) dp[i] = 2;
            else if(i == 3) dp[i] = 4;
            else{
                dp[i] = dp[i-1];
                if(i >= 2) dp[i] = dp[i] + dp[i-2];
                if(i >= 3) dp[i] = dp[i] + dp[i-3];
                dp[i] = dp[i]%10007;//每次都要模 10007 原来只在最后模10007了，就报错。感觉题目叙述也不清晰。
            }
        }
        return dp[K];
    }
}