#include "bits/stdc++.h"
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;

vector<int> ans(1000000+1,0);

void solve(){
   int n;
   cin>>n;
   cout<<ans[n]<<endl;
}

int main(){
    #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("out.txt", "w",stdout);
    #endif
    FAST;
    ans[1] = 1;
    ans[2] = 2;
    for (int i = 3; i <= 1000000; ++i)
    {
        ans[i] = (ans[i] + ans[i-1] + ans[i-2])%(1000000000+7);
    }
    int t = 1;
    cin>>t;
    while(t--)
     solve(); 
}