// Arup Guha
// 10/12/2022
// Computes g(n) mod 1000000007 for n upto 1000000000000 from Fall 2022 COT 3100 Homework #5 Question #4

/*** Key idea behind the solution is that if we multiply the following matrix:

     [3 1 1]    [g(n-1)]      [3*g(n-1)+g(n-2)+g(n-3)]     [g(n)  ]
     [1 0 0] x  [g(n-2)]   =  [g(n-1)                ]  =  [g(n-1)]
     [0 1 0]    [g(n-3)]      [g(n-2)                ]     [g(n-2)]

     This advances our "vector" of g values by 1.

     It follows that
            (n-3)
     [3 1 1]        [g(3)]      [[g(n) ]
     [1 0 0]     x  [g(2)]   =  [g(n-1)]
     [0 1 0]        [g(1)]      [g(n-2)]

     Thus, this solution uses fast matrix exponentiation to calculate the matrix exponent,
     and then takes the top row and multiplies it by the column matrix [3 2 2] to get the
     top right corner of the answer, which is g(n).
***/

#include <stdio.h>
#include <stdlib.h>

#define SIZE 3

#define MOD 1000000007ll

long long solve(long long n);
void fastModExpo(long long m[][SIZE], long long exp, long long res[][SIZE]);
void fillIdentity(long long a[][SIZE]);
void copy(long long res[][SIZE], long long a[][SIZE]);
void mult(long long a[][SIZE], long long b[][SIZE], long long c[][SIZE]);

int main(void) {

    // Read in number of cases.
    int nC;
    scanf("%d", &nC);

    // Process each case.
    for (int loop=0; loop<nC; loop++) {

        // Just read in the number for this case, and then output g(n) % MOD.
        long long n;
        scanf("%lld", &n);
        printf("%lld\n", solve(n));
    }

    return 0;
}

// Returns g(n) mod 1000000007.
long long solve(long long n) {

    // Cover base cases.
    if (n == 1 || n==2) return 2;
    if (n == 3) return 3;

    // Matrix for exponentiation.
    long long m[SIZE][SIZE] = {{3ll,1ll,1ll},{1ll,0ll,0ll},{0ll,1ll,0ll}};

    // Raise matrix to power n-3.
    long long res[SIZE][SIZE];
    fastModExpo(m, n-3, res);

    // This dot product is the final answer.
    long long ans = (res[0][0]*3+res[0][1]*2+res[0][2]*2)%MOD;
    return ans;
}

// Raises m to the power exp (mod all values by MOD) and stores answer in res.
void fastModExpo(long long m[][SIZE], long long exp, long long res[][SIZE]) {

    // Two base cases.
    if (exp == 0) {fillIdentity(res); return;}
    if (exp == 1) {copy(res, m); return;}

    // We exploit even exponent case to speed up work.
    if (exp%2 == 0) {
        long long half[SIZE][SIZE];
        fastModExpo(m, exp/2, half);
        mult(half, half, res);
        return;
    }

    // In the odd case, we just do m to the power exp-1 and multiply that by m.
    long long most[SIZE][SIZE];
    fastModExpo(m, exp-1, most);
    mult(most, m, res);
    return;
}

// Fills a with the identity matrix.
void fillIdentity(long long a[][SIZE]) {
    for (int i=0; i<SIZE; i++) {
        for (int j=0; j<SIZE; j++)
            a[i][j] = 0;
        a[i][i] = 1;
    }
}

// Copies a into res.
void copy(long long res[][SIZE], long long a[][SIZE]) {
    for (int i=0; i<SIZE; i++)
        for (int j=0; j<SIZE; j++)
            res[i][j] = a[i][j];
}

// Multiplies a and b storing result in c, overwriting what used to be in c.
void mult(long long a[][SIZE], long long b[][SIZE], long long c[][SIZE]) {

    for (int i=0; i<SIZE; i++) {
        for (int j=0; j<SIZE; j++) {
            c[i][j] = 0;
            for (int k=0; k<SIZE; k++)
                c[i][j] = (c[i][j] + a[i][k]*b[k][j])%MOD;
        }
    }
}