zero=sum([False,False])
one=sum([True,zero])
two=sum([one,one])
three=sum([one,two])
four=sum([one,three])
five=sum([one,four])
six=sum([one,five])
seven=sum([one,six])
eight=sum([one,seven])
nine=sum([one,eight])
ten=sum([one,nine])
def mul(a,b):
  r=zero
  while b:
    if b&one:
      r=sum([r,a])
    a<<=one
    b>>=one
  return r

mod=int(sum([pow(ten,nine),seven]))
def m(a,b):
  r=[[zero for j in range(len(b[zero]))] for i in range(len(a))]
  for i in range(len(a)):
    for k in range(len(b)):
      for j in range(len(b[zero])):
        r[i][j]=divmod(sum([r[i][j],mul(a[i][k],b[k][j])]),mod)[one]
  return r

def p(a,n):
  r=[[zero for j in range(len(a))] for i in range(len(a))]
  b=[]
  for i in range(len(a)):
    r[i][i]=one
    b.append(a[i][:])
  l=n
  while l>zero:
    if l&one:
      r=m(b,r)
    b=m(b,b)
    l>>=one
  return r

B=[[zero,two],[zero,one]]
A=[[zero,one],[one,one]]
T=int(input())
for i in range(T):
  print(m(p(A,int(input())),B)[zero][one])