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