There is a king in the lower left corner of the $n \times 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? \InputFile The first line contains the number of test cases $t~(1 \le t \le 1000)$. The next $t$ lines consist of single integer $n~(1 \le n \le 1000)$ --- the size of the board. \OutputFile For each test case output in a separate line the munber of ways to reach upper right corner of $n \times n$ board modulo $1000003$.