I Hate Combinatorics!

shep_com 16th December Programming...
Limits 1s, 512 MB

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

InputOutput
3
2
4
1000000
1
3
918091266
InputOutput
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.

Submit

Login to submit.

Statistics

97% Solution Ratio
arknaveEarliest, Dec '19
JIANEEFastest, 0.0s
JIANEELightest, 9.3 kB
Tahmid690Shortest, 226B
Toph uses cookies. By continuing you agree to our Cookie Policy.