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.
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