Задачи
Северо-восточный король Hard
Северо-восточный король Hard
В левом нижнем углу квадратной шахматной доски \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}).
\OutputFile
Для каждого \textbf{n} выведите одно целое число --- ответ на задачу.
Входные данные #1
2 2 3
Выходные данные #1
3 13