Random Walk That Never Goes Negative

Seonyeong stands at the origin of a very long line. In one move she can step one square to the left or one square to the right.

The number of random walks that use $2N$ moves and end at the starting square is $\binom{2N}{N}$. Coming back to the start forces the number of left moves to equal the number of right moves, so the walk makes $N$ moves right and $N$ moves left, and only their order is free.

In that version Seonyeong can stand on a negative coordinate. Write a program that counts the walks once the extra rule "never move to a negative coordinate" is added. For $N = 1$ she can walk $0 \to 1 \to 0$, but she cannot walk $0 \to -1 \to 0$.

The first line contains the number of test cases $T$ ($T \le 1{,}000$). Each of the next $T$ lines contains the value $N$ ($1 \le N \le 1{,}000{,}000$) of one test case.

For each test case, print the number of random walks that return to the starting square without ever visiting a negative coordinate, modulo 1,000,000,007. Print one answer per line.