Upper Right King (Hard)#3175
There is a king located in the lower left corner of an n \times n square chessboard. The king can move only one cell to the right, one cell up, or one cell up-right. Calculate the number of different ways for the king to reach the upper right corner of the board modulo .
The first line contains the integer (1 \leq T \leq 10000) — the number of test cases. Each of the next lines contains a single integer (1 \leq n \leq 10^6).
For each test case, print a single integer — the answer to the problem.
Example 1