T=int(input())
M=10**9+7
x=pow(3,M-2,M)
l=6

def seki(a,b):
  c=[[0]*l for i in range(l)]
  for i in range(l):
    for j in range(l):
      for k in range(l):
        c[i][j]+=a[i][k]*b[k][j]
        c[i][j]%=M
  return c

for _ in range(T):
  A=[
    [x,0,0,0,x,x],
    [0,x,0,x,0,x],
    [0,0,x,x,x,0],
    [1,0,0,0,0,0],
    [0,1,0,0,0,0],
    [0,0,1,0,0,0]
  ]
  B=[
    [1,0,0,0,0,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],
    [0,0,0,0,0,1]
  ]
  t=int(input())
  for i in range(30):
    if (t>>i)&1:
      B=seki(A,B)
    A=seki(A,A)
  print(B[0][0])