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** (**1** ≤ **t** ≤ **1000**). Next **t** lines consist of single integer **n** (**1** ≤ **n** ≤ **1000**) - 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**.

Input example #1

2 2 3

Output example #1

3 13