eolymp
Problems

North East King

North East King

There is a king in the lower left corner of the n × n checkmate board. The king can move one step right, one step up or diagonally one step up-right. How many ways are there for him to reach the upper right corner of the board?

Input

The first line contains the number of test cases t (1t1000). Next t lines consist of single integer n (1n1000) - the size of the board.

Output

For each test case output in a separate line the munber of ways to reach upper right corner of n × n board modulo 1000003.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
2
3
Output example #1
3
13