#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <bitset>
#include <bitset>
#include <cstring>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MOD = 1e9 + 7;
const int INTINF = 1e9;
const llong INF = 1e18;
const int MAXLOG = 17;

llong n;
llong d[MAXN];
llong v[MAXN];
llong ans[6][6];
llong buff[6][6];
llong base[6][6];
llong matrix[6][6] = 
{
    {0, 0, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0},
    {0, 1, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 1, 1, 0, 1},
    {0, 0, 0, 0, 1, 0},
};

inline void copy(llong a[][6], llong b[][6])
{
    for (int i = 0 ; i < 6 ; ++i)
    {
        for (int j = 0 ; j < 6 ; ++j)
        {
            a[i][j] = b[i][j];
        }
    }
}

inline void mult(llong a[][6], llong b[][6])
{
    // std::cout << "multiply\n";
    for (int i = 0 ; i < 6 ; ++i)
    {
        for (int j = 0 ; j < 6 ; ++j)
        {
            buff[i][j] = 0;
            for (int k = 0 ; k < 6 ; ++k)
            {
                buff[i][j] = (buff[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    copy(a, buff);
}

inline void power(llong n)
{
    for (int i = 0 ; i < 6 ; ++i)
    {
        for (int j = 0 ; j < 6 ; ++j)
        {
            base[i][j] = matrix[i][j];
        }
    }

    memset(ans, 0, sizeof(ans));
    for (int i = 0 ; i < 6 ; ++i) ans[i][i] = 1;
    for (int log = 0 ; (1ll << log) <= n ; ++log)
    {
        if (n & (1ll << log)) mult(ans, base);
        mult(base, base);
    }
}

void solve()
{ 

    if (n <= 5)
    {  
        v[0] = 1;
        d[0] = 1;
        for (int i = 1 ; i <= n ; ++i)
        {
            d[i] = 0;
            v[i] = d[i - 1];
            if (i > 1) 
            {
                d[i] += v[i - 2];
            }
            
            if (i > 2)
            {
                v[i] += v[i - 2];
                d[i] += d[i - 2];
            }

            v[i] %= MOD;
            d[i] %= MOD;
        }

        std::cout << d[n] + v[n] << '\n';
    } else
    {
        llong order[] = {1, 1, 1, 0, 2, 1};
        power(n - 4);

        llong answer = 0;
        for (int j = 0 ; j < 6 ; ++j)
        {
            answer += ans[j][2] * order[j];
            answer += ans[j][5] * order[j];
            answer %= MOD;
        }

        std::cout << answer << '\n';
    }
}

void input()
{
    std::cin >> n;
}

void fastIOI()
{   
    freopen("penguin.in", "r", stdin);
    freopen("penguin.out", "w", stdout);
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int tests;
int main()
{
    fastIOI();
    std::cin >> tests;

    while (tests--)
    {
        input();
        solve();
    }

    return 0;
}