D

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)

int main()
{
    int N = 1e5 + 1;
    int MOD = 1e9 + 7;

    vector<ll int> x(N+10);
    vector<ll int> y(N+10);

    x[1] = 1;

    for(int i=0; i<N; i++)
    {
        (x[i+2] += x[i]) %= MOD;
        (x[i+3] += x[i]) %= MOD;
        (x[i+4] += x[i]) %= MOD;

        (y[i+2] += y[i]) %= MOD;
        (y[i+3] += y[i]) %= MOD;
        (y[i+4] += y[i]) %= MOD;

        x[i+1] += y[i];
        y[i+1] += x[i];
    }

    _test
    {
        int l;
        cin>>l;

        if(l==1 || l==2)  cout<<1<<"\n";
        else if(l == 3)   cout<<3<<"\n";
        else              cout<<(x[l]+x[l-1]+x[l-2]+x[l-3])%MOD<<"\n";
    }
}