Our chef has been assigned a task to make a necklace of length N, from gold, diamond and platinum.There is single kind of gold, two types of diamond and three types of platinum available.
A necklace can be represented as strings of the form (G)∗(D1|D2)∗(P1|P2|P3)∗$ (G)*(D1|D2)*(P1|P2|P3)* $ where (x|y) means we can use x or y and ∗$ * $ means we can repeat the previous parenthesized expression 0 or more times.
Instead of making necklace he choose to count all such distinct necklaces possible for a given length N.

-----Input:-----
-The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
-Only line of every test case contains an integer N$N$ denoting the length of the necklace required.

-----Output:-----
For each test case, print the number of all such distinct necklaces, with given length. As the number can be really large, print it modulo  109+7$10^{9}+7$.

-----Constraints-----
- 1≤T≤10000$1 \leq T \leq 10000$
- 2≤N≤1000000000$2 \leq N \leq 1000000000$
- String S$S$ consists of only upper case english alphabets.

-----Subtasks-----
- 20 points : 1≤N≤5$1 \leq N \leq 5$
- 70 points : Original$Original$ Constraints$Constraints$

-----Sample Input:-----
2
1
2

-----Sample Output:-----
6
25

Difficulty: interview

Starter code:

Solutions:
t=int(input())
for _ in range(t):
    n=int(input())
    p=10**9+7
    a=(pow(3,n+1,p)-1)
    
    b=(pow(2,n+1,p)-1)
  
    print((((3*a)//2)%p-(2*(b))%p+p)%p)

t=int(input())
for _ in range(t):
    n=int(input())
    p=10**9+7
    a=(pow(3,n+1,p)-1)
    b=(pow(2,n+1,p)-1)
    print(((3*a)//2)%p-(2*(b))%p)

t=int(input())
for _ in range(t):
    n=int(input())
    p=10**9+7
    a=(pow(3,n+1,p)-1)
    b=(pow(2,n+1,p)-1)
    print(((3*a)//2)%p-(2*(b))%p)

tc=int(input())
while tc>0:
    tc-=1
    mod_inv=500000004
    mod=1000000007
    n=int(input())
    res=((4500000036*(pow(3,n,mod)-1))%mod)-(4*(pow(2,n,mod)-1))
    print((res+1)%mod)


import math
import bisect
import itertools
import sys
mod=10**9 +7
'''fact=[1]*1001
ifact=[1]*1001
for i in range(1,1001):
    fact[i]=((fact[i-1])*i)%mod
    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod
def ncr(n,r):
    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod
def npr(n,r):
    return (((fact[n]*ifact[n-r])%mod))
    '''
'''def mindiff(a):
    b=a[:]
    b.sort()
    m=10000000000
    for i in range(len(b)-1):
        if b[i+1]-b[i]<m:
            m=b[i+1]-b[i]
    return m
    '''
'''def lcm(a,b):
    return a*b//math.gcd(a,b)

    '''
    
'''def merge(a,b):
    i=0;j=0
    c=0
    ans=[]
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            c+=len(a)-i
            j+=1
    ans+=a[i:]
    ans+=b[j:]
    return ans,c
def mergesort(a):
    if len(a)==1:
        return a,0
    mid=len(a)//2   
    left,left_inversion=mergesort(a[:mid])
    right,right_inversion=mergesort(a[mid:])
    m,c=merge(left,right)
    c+=(left_inversion+right_inversion)
    return m,c
    
'''
'''
def is_prime(num):
    if num == 2: return True
    if num == 3: return True
    if num%2 == 0: return False
    if num%3 == 0: return False
    t = 5
    a = 2
    while t <= int(math.sqrt(num)):
        if num%t == 0: return False
        t += a
        a = 6 - a
    return True
 '''
a1=[2,6]
a2=[3,18]
a=[]
for i in range(100000):
    a2.append(((a2[-1]+a1[-1]+1)*3)%mod)
    a1.append(((a1[-1]+1)*2)%mod)
for i in range(100000):
    a.append((a1[i]+a2[i]+1)%mod)
t=int(input())
#print(a)
for i in range(t):
    n=int(input())
    print(a[n- 1])

t=int(input())
for _ in range(t):
    n=int(input())
    p=10**9+7
    a=(pow(3,n+1,p)-1)
    b=(pow(2,n+1,p)-1)
    print((((3*a)//2)%p-(2*(b))%p)%p)

T=int(input())
while T>0:
    T-=1
    mod_inv=500000004
    mod=1000000007
    n=int(input())
    ans=((4500000036*(pow(3,n,mod)-1))%mod)-(4*(pow(2,n,mod)-1))
    print((ans+1)%mod)


import math
import bisect
import itertools
import sys
mod=10**9 +7
'''fact=[1]*1001
ifact=[1]*1001
for i in range(1,1001):
    fact[i]=((fact[i-1])*i)%mod
    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod
def ncr(n,r):
    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod
def npr(n,r):
    return (((fact[n]*ifact[n-r])%mod))
    '''
'''def mindiff(a):
    b=a[:]
    b.sort()
    m=10000000000
    for i in range(len(b)-1):
        if b[i+1]-b[i]<m:
            m=b[i+1]-b[i]
    return m
    '''
'''def lcm(a,b):
    return a*b//math.gcd(a,b)

    '''
    
'''def merge(a,b):
    i=0;j=0
    c=0
    ans=[]
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            c+=len(a)-i
            j+=1
    ans+=a[i:]
    ans+=b[j:]
    return ans,c
def mergesort(a):
    if len(a)==1:
        return a,0
    mid=len(a)//2   
    left,left_inversion=mergesort(a[:mid])
    right,right_inversion=mergesort(a[mid:])
    m,c=merge(left,right)
    c+=(left_inversion+right_inversion)
    return m,c
    
'''
'''
def is_prime(num):
    if num == 2: return True
    if num == 3: return True
    if num%2 == 0: return False
    if num%3 == 0: return False
    t = 5
    a = 2
    while t <= int(math.sqrt(num)):
        if num%t == 0: return False
        t += a
        a = 6 - a
    return True
 '''
a1=[2,6]
a2=[3,18]
a=[]
for i in range(100000):
    a2.append(((a2[-1]+a1[-1]+1)*3)%mod)
    a1.append(((a1[-1]+1)*2)%mod)
for i in range(100000):
    a.append(a1[i]+a2[i]+1)
t=int(input())
for i in range(t):
    n=int(input())
    print(a[n- 1])

t=int(input())
for _ in range(t):
    n=int(input())
    p=10**9+7
    a=(pow(3,n+1,p)-1)%p
    b=(pow(2,n+1,p)-1)%p
    print((((3*a)//2)%p-(2*(b))%p)%p)


t=int(input())
mod=10**9+7
inverse=5*(10**8)+4

for i in range(t):
	n=int(input())
	temp1=pow(3,n+2,mod)
	temp2=pow(2,n+3,mod)
	a=(temp1-temp2+1)%mod
	a=(a*inverse)%mod
	
	print(a)	

t=int(input())
ans=[]
for i in range(t):
	n=int(input())
	c=0
	for j in range(n+1):
		for k in range(0,n-j+1):
			c+=(2**k)*(3**j)
	ans.append(c)
for i in ans:
	print(i)



t=int(input())
mod=10**9+7
for i in range(t):
	n=int(input())
	ans=0
	for j in range(n+1):
		temp1=pow(3,j,mod)
		temp2=(pow(2,n+1-j,mod)+(mod-1))%mod
		temp3=(temp1*temp2)%mod
		ans=(ans+temp3)%mod
	print(ans)	


t=int(input())
mod=1000000007
while t:
    t-=1
    n=int(input())
    ans=(2*pow(3,n+1,mod))%mod-pow(2,n+2,mod)-((pow(3,n+1,mod)-1)*(500000004))%mod
    ans%=mod
    print(ans)


MOD = int(1e9 + 7)
for _ in range(int(input())):
    n = int(input()) + 1
    res = (((3*pow(3, n, MOD) - 3) % MOD) * 500000004)% MOD
    res = (res - (2*(pow(2, n, MOD) - 1)) % MOD) % MOD
    print(res)

T=int(input())
while T>0:
    T-=1
    n=int(input())
    ans=0;
    for i in range(n+1):
        for j in range(n-i+1):
            k=(n-i-j)
            # print(i,j,k)
            ans+=((pow(2,j,1000000007)*pow(3,k,1000000007))%1000000007)
    print(ans)