North East King#3174
There is a king in the lower left corner of an n \times n square chessboard. The king can move one step to the right, one step up, or one step diagonally up-right. Count the number of ways the king can reach the upper right corner of the board modulo .
The first line contains the number of test cases (1 \leq t \leq 1000). Each of the next lines contains a single integer (1 \leq n \leq 1000).
For each test case, output the number of possible ways to reach the upper right corner of the n \times n board modulo .
Example 1