У лівому нижньому куті квадратної шахової дошки \textbf{n}×\textbf{n} знаходиться король. Він може ходити лише на одну клітинку праворуч, вгору, чи праворуч вгору. Порахуйте кількість способів, якими король може дійти до правої верхньої клітинки дошки по модулю \textbf{1000003}. \InputFile Перший рядок входу містить число \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10000}) --- кількість тестів. Наступні \textbf{T} рядків містять по одному цілому числу \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}). \InputFile Для кожного \textbf{n} виведіть одне ціле число --- відповідь до задачі.