В левом нижнем углу квадратной шахматной доски \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} выведите одно целое число --- ответ на задачу.