AKVDDN03 - Butters solves Recurrences 450 pts

no tags 

Butters likes to solve Recurrence Relations. He wants to solve them really fast. He got this relation:

    F(n) = 2 * F(n - 1) + 3 * F(n - 2), with F(1) = 1 and F(2) = 2

So the series becomes:

    1  2  7  20  61 ...

So the first term is 1, 2nd term is 2, 3rd term in 7 and so on. He wants to know the Nth term of this series. Since the answer can be really large, he wants to find it modulo 1000000007.

Input

First line will contain "T" the number of test cases. Each of the next "T" lines will contain an integer N, the term which Butters wants to find.

Output

For each test case print the Nth term of this series modulo 1000000007.

Constraints

1 <= T <= 10^5

1 <= N <= 10^9

Example

Input:
5
1
5
10
2
1000

Output:
1
61
14762
2
14222048


Added by:Ankit Kumar Vats
Date:2013-08-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self