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⁹ + 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¹²