#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

#define MOD (1000000007LL)

typedef long long int lint;
lint N;
typedef vector<vector<lint> > MATRIX;


//bruteforce teszthez
lint stupid(){
    lint ret[5] = {0,1,2,3,5};
    lint sum = 11;

    if(N==4)return sum;

    for(lint i =0;i<N-4;i++){
        lint n = (((ret[4] + ret[3])%MOD) + ret[1])%MOD;

        ret[1] = ret[2];
        ret[2] = ret[3];
        ret[3] = ret[4];
        ret[4] = n;

        sum = (sum+n);
        if(sum > 1000000007){sum%=MOD;}
    }

    return sum;
}

MATRIX getMagicMatrix(){
    MATRIX magic = {
        {1,1,1,0,1,0}, // SUM
        {0,1,1,0,1,0},
        {0,1,0,0,0,0},
        {0,0,1,0,0,0},
        {0,0,0,1,0,0},
        {0,0,0,0,1,0}
    };
    return magic;
}

int getNOfMatrix(const MATRIX &m){
    return m.size();
}

int getMOfMatrix(const MATRIX &m){
    return m[0].size();
}

MATRIX getNMZeroMatrix(const int n,const int m){
    MATRIX result(n);
    for(int i=0;i<n;i++){
        result[i].resize(m);
    }
    return result;
}


void printm(const MATRIX &m){
    for(auto v : m){
        for(auto elem: v){
            printf("%lld\t",elem);
        }
        printf("\n");
    }
}


MATRIX matrixmul(const MATRIX &a,const MATRIX &b){
    assert(getMOfMatrix(a) == getNOfMatrix(b));

    int rowa = getNOfMatrix(a);
    int cola = getMOfMatrix(a);

    MATRIX result = getNMZeroMatrix(rowa,getMOfMatrix(b));

    for(int resultcolindex = 0;resultcolindex<getMOfMatrix(b);resultcolindex++){
        for(int rowina = 0;rowina<rowa;rowina++){
            for(int c = 0;c<cola;c++){
                result[rowina][resultcolindex] = (result[rowina][resultcolindex] +  (( (a[rowina][c]%MOD) * (b[c][resultcolindex]) % MOD) % MOD) )% MOD;
            }
        }
    }

    return result;
}



//A^e
MATRIX matrixpow(MATRIX matrix, lint e){
    MATRIX pows[40];
    lint e_ = e;

    MATRIX current = matrix;

    bool notbegin = true;
    MATRIX result;

    int pos = 0;

    while(e_>0){
        if(e_&1){
            if(notbegin){
                result = current;
                notbegin = false;
            }else{
                result = matrixmul(result,current);
            }
        }

        e_>>=1;
        current = matrixmul(current,current);
        pos++;
    }

    return result;
}


lint getsumn(const lint n){
    if(n==0x4){return 11;}
    if(n==0x5){return 20;}

    const MATRIX magic =matrixpow(getMagicMatrix(),n-4);

    const MATRIX b = {
        {11}, // KEZDETI SUM
        {5},
        {3},
        {2},
        {1},
        {0}
    };

    const MATRIX &result = matrixmul(magic,b);
    return result[0][0];
}


int main(){
    int tcase;
    scanf("%d",&tcase);

    while(tcase--){
        scanf("%lld",&N);
        printf("%lld\n",getsumn(N));
    }

    return 0;
}