#include <iostream>
using namespace std;

const int N=1000000+1;
long long freq[N];

void solve()
{
    freq[0]=0;
    freq[1]=1;
    freq[2]=2;
    freq[3]=3;

    long long answer=1000000000+7;

    for(int i=4;i<N;i++){
        freq[i]=(freq[i]+freq[i-1]+freq[i-2])%answer;
    }
}

int main()
{
    std::ios_base::sync_with_stdio(0); std::cin.tie(nullptr); std::cout.tie(nullptr);
    solve();

    int t;cin>>t;
    for(int i=0;i<t;i++){
        int n;cin>>n;
        cout<<freq[n]<<endl;
    }

    return 0;
}
//*/
/*
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
    string str;
    cout << "Please enter a  word: "; //ask for input
    cin >> str;
    sort(str.begin(), str.end());
    int it=1;
    do {
        cout <<it<<" "<<str << '\n';
        it++;

    } while (next_permutation(str.begin(), str.end()));
    cout<<"End"<<endl;
    }
}
//*/