Robot

There is a robot on the origin point of an axis.Every second, the robot can move right one unit length or do nothing.If the robot is
on the right of origin point,it can also move left one unit length.A route is a series of movement. How many different routes there are
that after $n$ seconds the robot is still located on the origin point?
The answer may be large. Please output the answer modulo $1,000,000,007$

There are multiple test cases. The first line of input contains an integer $T (1\leq T\leq 100)$ indicating the number of test cases. For each test case:

The only line contains one integer $n(1\leq n \leq 1,000,000)$.

For each test case, output one integer.

3
1
2
4

1
2
9

BestCoder Round #81 (div.2)