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

int32_t main(){
    int t;cin>>t;
    vector<int> dp(10010,0);
    dp[0]=1;dp[1] = 1;dp[2] = 2;
    for(int i=3;i<=10001;i++){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        dp[i]%=1000007;
    }
    while(t--){
        int n;cin>>n;
        cout<<dp[n]<<endl;
    }
}