I Hate Combinatorics!

Rick and Morty are being hunted by the galactic government. They ran away to the cell dimension. The cell dimension is made up of N cells distributed in 2 rows and N/2 columns (N is always even). The cells are numbered from 0 to N-1. Rick and Morty are currently in cell number 0. To escape from this dimension, they have to reach cell N-1. Why you ask? Because the portal gun only works in cell N-1. They can only move to an adjacent cell to the right of their current cell. Therefore the 4 types of available moves are :

D = downward diagonal

U = upward diagonal

H = high horizontal step

L = lower horizontal step

Because Rick and Morty's spaceship is out of fuel, they need to refuel. The fuel price is determined rather weirdly in the cell dimension. The cost of fuel necessary to reach from cell 0 to cell N-1 is the total number of routes to go from cell 0 to cell N-1. Rick is a genius but he is stumped in this case. Help him calculate exactly how much fuel he needs to buy.

Input

The input consists of an integer T, the number of test cases.

This is followed by T lines, each consisting of a single even integer N, the number of cells in cell land.

1<=T<=105
2<=N<=106

Output

Print T lines. In each line, print the cost of the fuel to go from cell number 0 to cell number N-1, which is equal to the number of routes to go from cell 0 to N-1.

As the solution can be a very big number, print the answer modulo 1000000007.

Samples

3
2
4
1000000

1
3
918091266

1
4

3

In case of sample test 2:

There are 3 possible routes to go from cell 0 to cell 3, as illustrated in the picture above.