newsch

#include <iostream>
#include <cstring>
#define MOD 1000000007
using namespace std;
int a[80][10][10], sol[10][10], mat[10][10], t, i, l, c, j;
long long n, p;
int main()
{
    cin >> t;
    a[0][1][1] = -1;
    a[0][3][3] = 3;
    a[0][1][2] = a[0][3][4] = 1;
    a[0][3][1] = 3;
    for(i = 0; (1LL<<i) <= 1000000000LL; i++)
    {
        for(l = 1; l <= 4; l++)
            for(c = 1; c <= 4; c++)
                for(j = 1; j <= 4; j++)
                {
                    a[i+1][l][c] += ((long long)a[i][l][j]*a[i][j][c])%MOD;
                    if(a[i+1][l][c] > MOD) a[i+1][l][c] -= MOD;
                }
    }
    while(t--)
    {
        cin >> n;
        p = n;
        memset(sol, 0, sizeof(sol));
        sol[1][1] = sol[2][2] = sol[3][3] = sol[4][4] = 1;
        for(i = 0; (1LL<<i) <= p; i++)
        if((1LL<<i)&p)
        {
            memset(mat, 0, sizeof(mat));
            for(l = 1; l <= 4; l++)
                for(c = 1; c <= 4; c++)
                    for(j = 1; j <= 4; j++)
                    {
                        mat[l][c] += ((long long)sol[l][j]*a[i][j][c])%MOD;
                        if(mat[l][c] > MOD) mat[l][c] -= MOD;
                    }
            memcpy(sol, mat, sizeof(mat));
        }
        cout << 4*sol[1][2] << "\n"; //MODULO!

    }
    return 0;
}
//
//4*3*3*3*2
//4*3*3*3*3*3=
//
//D[i] = prod[i-1] * 3 - D[i-1]
//
//(D[i], D[i-1], prod[i], prod[i-1]) *
// (12 4 12 4)
// -1 1 0 0
// 0  0 0 0
// 3  0 3 1
// 0  0 0 0
// (24 12 36 12)
//
//= (D[i+1] D[i] prod[i+1] prod[i])