Северо-восточный король Hard

В левом нижнем углу квадратной шахматной доски n×n находится король. Он может ходить только на одну клетку вправо, вверх, или вправо вверх. Посчитайте количество способов, которыми король может дойти до правой верхней клетки доски по модулю 1000003.

Входные данные

Первая строка входа содержит число T (1 ≤ T ≤ 10000) — количество тестов. Следующие T строк содержат по одному целому числу n (1 ≤ n ≤ 10^6).

Выходные данные

Для каждого n выведите одно целое число — ответ на задачу.

Примеры