King Tle4Ever of Time Limit Exceeded has recently appointed Ram as his new cashier. To get this job Ram has paid 1 SegFault (SegFault is the currency of Time Limit Exceeded). Today is his first day at work and he will get 1 SegFault for his salary. As Tle4Ever thought this is really less so for the coming days he thought of paying Ram a good amount of SegFaults. For the i^th day Ram gets twice the SegFaults for (i-1)^th, thrice the SegFaults for (i-2)^th day and 3ⁱ as bonus for working on i^th day.

As you can see Ram is getting a huge amount of SegFaults, he wants to calculate how much SegFaults will he get on k^th day. As he is busy working for King, he asks you to tell him the SegFaults he will get on k^th day. As the no of SegFaults can be large and to save you from outputting random values, I ask you to print ans % 10⁹ + 7.

[Input]
First line of input consists of single integer t denoting number of test cases.
Next t line contains single integer k denoting the k^th day.

[Output]
For each test case print single integer containing ans % 10⁹ + 7.

[Constraints]
1<=t<=10⁵
0<=k<=10⁹