#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll binomialCoeff(ll n, ll k) 
{ 
    ll res = 1; 
  
    if (k > n - k) 
        k = n - k; 
  
    for (ll i = 0; i < k; ++i) { 
        res *= (n - i) % 1000000007; 
        res /= (i + 1); 
    } 
  
    return res; 
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while(T--)
    {
        ll S;
        cin >> S;
        int X;
        switch(S % 3)
        {
            case 0:
                X = 0;
                break;
            case 1:
                X = 2;
                break;
            case 2:
                X = 1;
                break;
        }
        ll NPlusK = (S-2*X)/3;
        ll ThreeNPlusK = S-(2*X);

        ll out = 0;
        //cout << "N+K: " << NPlusK << " X: " << X << endl;
        for(ll i = 0;i<NPlusK+1;i++)
        {
            //cout << i << " -> " << binomialCoeff(S, 3*i+X) << "\n";
            //cout << "3i+X: " << 3*i+X << '\n';
            out += binomialCoeff(S, (NPlusK-i)*3 + X);
            out %= 1000000007;
        }

        //cout << NPlusK << '\n';
        cout << out % 1000000007 << '\n';
        //cout << "1-től n+k-ig s alatt k summája" << '\n';
    }

    return 0;
}