SP7859 ADV04B1 - Upper Right King (Hard)

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 one step up-right. How many ways are there for him to reach the upper right corner of the board?

The first line of input contains number T - the amount of test cases. Next T lines consist of single integer n - the size of the board.

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