Alook was composing magical spells for his mage master. The mage was good at spellcasting but since spell design requires intricate mathematics, this task was given to Alook who had the gift of numbers.

The power contained in a spell is a function of its lexicographical structure, which is why Alook wants to extensively test spells of difference lexicographical structures.
Spells are composed of 2 types of lexemes : long and short; a short lexeme is one phoneme long while a long lexeme is two phonemes long. A third special type of lexeme of length 2 phonemes can be used only at the beginning of a spell.

Additionally, each phoneme can be uttered in two ways :in a 'high' or a 'low' note.
There are still, however only 2 types of lexemes and not 6 as lexemes are characterized only on the basis of their length and not their constituent phonemes. Phonemes are spoken while lexemes are written. Lexemes enforce a substructure on phonemes, but phonemes do not enforce any structure on lexemes.

Every day, Alook writes down spells of all possible lexicographical structures, upto n phonemes in length. His master utters all possible phonetic variations of every written spell to service his oral fixation. Given n, you have to tell how many phonetically different spells the mage casts.

Read about lexeme here : Lexeme
Read abour phoneme here : Phoneme

[Input]
First line contains and integer t denoting number of test cases.
Each test consists of single line containing integer n denoting length.

[Output]
For each test case output single line denoting ans.

NOTE: As ans can be large output the ans by taking mod with 10^9 + 7.

[Constraints]
1 ≤ t ≤ 100
1 ≤ n ≤ 1000000000

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
2
14

Explanation

for n=1
No. of lexicographically different spells of length 1 : 1 {S}
No. of phonetic variations : 2 {H,L} where H denotes High and L denotes Low
Therefore total no.of different spells = 1*2 = 2
def matmult(a,b,c,M):
	#/multiply matrix a and b. put result in c

    
    for i in xrange(2):
    
        for j in xrange(2):
        
            c[i][j]=0
            for k in xrange(2):
            
                c[i][j]+=(a[i][k]*b[k][j])
                c[i][j]=c[i][j]%M
            
        
    
 

def matpow(Z,n,ans,M):
#find ( Z^n )% M and return result in ans

 
    temp=[[0,0],[0,0]]
    #assign ans= the identity matrix
    ans[0][0]=1
    ans[1][0]=0
    ans[0][1]=0
    ans[1][1]=1
    
    while(n>0):
    
        if(n&1):
        
            matmult(ans,Z,temp,M)
            for i in xrange(2):
                for j in xrange(2):
                    ans[i][j]=temp[i][j]
        
        matmult(Z,Z,temp,M)
        for i in xrange(2):
            for j in xrange(2):
                Z[i][j]=temp[i][j]
 
 
        n=n/2
    
    
     

def findFibonacci(n,M):

     
    fib=0
    ini = [0,2,12]
    
    if(n>2):
    
    	n+=2
        Z=[[2,4],[1,0]]
        result=[[0,0],[0,0]]
        #modify matrix a[][] for other recurrence relations
        matpow(Z,n-2,result,M)
        #fib2=((result[0][0]*ini[2])%M + (result[0][1]*ini[1])%M)%M
        #fib1=((result[1][0]*ini[2])%M + (result[1][1]*ini[1])%M)%M
        #final multiplication of Z^(n-2) with the initial terms of the series
        fib2 = result[0][0]*ini[2] + result[0][1]*ini[1]
        fib1 = result[1][0]*ini[2] + result[1][1]*ini[1]
        x = 400000003
        fib = (((fib2-fib1-ini[2]+ini[1])%M)*x)%M
    
    else:
    
        fib=ini[n]+ini[n-1]
    
         
    return fib%M
    

def findFibonacci2(n,M):

     
    fib=0
    ini = [0,2,12]
    
    if(n>2):
    
    	#n+=2
        Z=[[2,4],[1,0]]
        result=[[0,0],[0,0]]
        #modify matrix a[][] for other recurrence relations
        matpow(Z,n-2,result,M)
        fib=((result[0][0]*ini[2])%M + (result[0][1]*ini[1])%M)%M
        #fib1=((result[1][0]*ini[2])%M + (result[1][1]*ini[1])%M)%M
        #final multiplication of Z^(n-2) with the initial terms of the series
        
        #fib = ((fib2-fib1-ini[2]+ini[1])%M)5/
    
    else:
    
        fib=ini[n]
    
         
    return fib



def main():

	
	
	M = 1000000007
	
	for _ in xrange(int(raw_input())):
	
		n=int(raw_input())
		#ans =0 
		#for i in xrange(1,n+1):
		#	ans = (ans + findFibonacci2(i,M))%M
		
		print findFibonacci(n,M)
	

    
main()