There is a king in the lower left corner of the \textbf{n}×\textbf{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? \InputFile The first line of input contains number \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10000}) --- the amount of test cases. Next \textbf{T} lines consist of single integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}) - the size of the board. \OutputFile For each test case output the munber of ways to reach upper right corner of \textbf{n}×\textbf{n} board modulo \textbf{1000003}.