The Famous Three

0

0 votes
Problem

Famous Santa Banta and Ghanta are the chief guest of "Comedy Night in Varchas" this time. FOC team has worked hard to make the arrangements for "The Famous Three". The Famous three as we called them are known for their yearly tour( fu**ing weird tour).Tour description is as follows.

  • Santa starts the tour. He travels 1 km. Then Banta travels 2 km. Then Ghanta travels 6 Km. This is complete one cycle.
  • After that Santa travels 2 * distance travelled by Banta previously + 2 * distance travelled by Ghanta previously.
  • After that Banta travels 2 * distance travelled by Ganta previously + 2 * distance travelled by Santa previously.
  • After that Ghanta travels 2 * distance travelled by Santa previously + 2 * distance travelled by Banta previously.This is another complete cycle.
  • This happens in cycle.

Given a number n , find how much distance % (10^9+7) travelled by them in nth cycle. Here % is modulo(remainder) operator.

For Example:

For n =1 , distance travelled would be 1 + 2 + 6 = 9 km.

For n =2 , it would be (2 * 2 + 2 * 6) + (2 * 6 + 2 * (2 * 2 + 2 * 6)) + (2 * (2 * 2+ 2 * 6) + 2 * (2 * 6 + 2 * (2 * 2 + 2 * 6))) = 180 km.

Input

First line contains number of test cases(T)

Next T line contains one integer n in each line

Ouput

N lines. For each test case, output a single integer containing the answer to the corresponding test case.

n<=10^9

T<=100000

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?