Gandalf the Grey is in trouble as Saurons eye Rearrived in the middle
    world. Now he has to prepare for the war, But in order to defeat Sauron 
    he has to know the power of saurons eye on the day in which he wants to
    attack.
    
    According to the Elves(Good Friends of Gandalf),Gandalf came to know that
    saurons eye power on current day is equal to 3 time to its power on
    previous day minus the power on a day before previous day.

    Now Gandalf ask Frodo to give him the power of the Saurons Eye on nth day, but poor Frodo is not
    good in mathematics so he ask for help from you.
    Given the nth day you have to give Frodo power of Saurons eye on 
    that day mod 10^9 + 7.
    
Note You can assume the power of sauron eye is 1 on 1st day 
     and 3 on 2nd day.
Input

The first line of the input contains an integer T, the number of test cases. Each of the following T lines contains a single integer N 
denoting the day for which you have to calculate power of Saurons Eye.
Output

For each test case output a single integer in a separate line, the answer for the corresponding test case.

Constraints
1 ≤ T ≤ 10000
1 ≤ N ≤ 10^12SAMPLE INPUT
2
1
3

SAMPLE OUTPUT
1
8

Explanation

First test Case: As indicated in the question power on first day is 1
Second test Case: Answer will be 3*3-1=8.
import sys

M = 10 ** 9 + 7
MAX_T = 10000
MAX_N = 10**12
_CUTOFF = 1536
cache = {}
results = []

def do_calc(n):
  if n in cache:
    return cache[n]

  the_matrix = [3, 1, -1, 0]
  result = power(the_matrix, n)[1]

  if n not in cache:
    cache[n] = result

  return result

def power(matrix, n):
  result = [1, 0, 0, 1]

  while (n != 0):
    if n % 2 != 0:
      result = multiply(result, matrix)
    n /= 2
    matrix = multiply(matrix, matrix)

  return result


def multiply(x, y):

  a = ((kply(x[0] % M, y[0] % M)) % M + (kply(x[1] % M,y[2] % M)) % M) % M
  b = ((kply(x[0] % M, y[1] % M)) % M + (kply(x[1] % M,y[3] % M)) % M) % M
  c = ((kply(x[2] % M, y[0] % M)) % M + (kply(x[3] % M,y[2] % M)) % M) % M
  d = ((kply(x[2] % M, y[1] % M)) % M + (kply(x[3] % M,y[3] % M)) % M) % M


  return [a, b, c, d];


def kply(x, y):
  if x.bit_length() <= _CUTOFF or y.bit_length() <= _CUTOFF:  # Base case
    return x * y
  
  else:
    n = max(x.bit_length(), y.bit_length())
    half = (n + 32) // 64 * 32
    mask = (1 << half) - 1
    xlow = x & mask
    ylow = y & mask
    xhigh = x >> half
    yhigh = y >> half
    
    a = kply(xhigh, yhigh)
    b = kply(xlow + xhigh, ylow + yhigh)
    c = kply(xlow, ylow)
    d = b - a - c
    return (((a << half) + d) << half) + c


input_text = map(int, sys.stdin.readlines())
num_tests = input_text[0]
input_nums = [x for x in input_text[1:num_tests+1] if x >= 1 and x <= MAX_N]
input_text = None # don't need this anymore
max_num = max(input_nums)
do_calc(max_num)

for i in input_nums:
  results.append(do_calc(i))


for r in results:
  print r