Our well known FULIA has some amazing powers. One day he put 1 candy in a bag and on next day he do some magic, after that due to his amazing powers the number of candies in the bag starts increasing day by day according to the following formula.

C(N) = 2 * C(N - 1) + 3 * C(N - 2)

C(N) denotes number of candies in the bag at Nth day. C(1) = C(2) = 1.

C(N - 1) and C(N - 2) denotes the number of candies on N-1^th and N-2^th day respectively.

Fulia is weak at maths and can't deal with big numbers, so he want you to write a program to count number of candies C(N) % MOD in the bag at Nth day, where MOD = 1000000007.

Input

First line of input consists of T (number of test cases) then T lines follows, each contains a single integer denoting the day N.

Output

Output the value of C(N) % MOD.

Example

Input:
4
1
2
3
4

Output:
1
1
5
13

Constraints

1 ≤ T ≤ 10³

1 ≤ N ≤ 10⁹