For his training, Digo is asked to solve the following challenge.

There is a mock terrorist situation. There are N terrorists and Digo is teamed up with his friend Sharry. They have to kill all the terrorists. Since this was too easy a task for this dynamic duo, Digo decided to have some fun with this challenge. At any given instant, Digo wants that the number of terrorists killed by him should be more than those killed by Sharry. The terrorists come in a fixed order. Any terrorist can be killed by either Digo or Sharry. Give the total number of ways in which the terrorists can be killed by them such that at every instant terrorists killed by Digo is more than the number of terrorists killed by Sharry.

Give your answer modulo 10^9+7.

Input

The first line consists of a single integer T, denoting the number of test cases.

T lines follow each consisting of an integer N denoting the total number of terrorists.

Output

For each test case print the total number of possible ways modulo 10^9 + 7.

Constraints

1 <= t <= 100000
1 <= n <= 1000000

Sample

Input:
2
1
3

Output:
1
2