Alan threw a party and invited all her close friend to it. Let us suppose there were 2n people in the party and all of them were sitting across a round table.
The host asked them to shake hands with the condition that no two hands should cross each other i.e if 4 people are sitting then 1st person cannot shake hands with 3rd as that will cross with the hands of 2nd and 4th person.
The host wants to know the no of ways in which her friends can shake hands with each other. So your task is to help Alan in finding this.

Input
First line of input will contain no of test cases t, followed by t lines each containing an integer N(<1000).

Output
For each test case, output a single integer which is the no of ways in which persons can shake hands for that particular N. output the answer %100003.

Example
Input:
2
2
4
Output:
2
14

见题面

见题面