computing-salary

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^i 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^9 + 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^9 + 7.
[Constraints]
1 ≤ t ≤ 10^5
0 ≤ k ≤ 10^9

SAMPLE INPUT
4
2
3
6
10

SAMPLE OUTPUT
8
46
2870
409652

Source: hackerearth | Difficulty: MEDIUM
Tags: Combinatorics


Solutions: