eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Триомино

Триомино

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Сколькими способами можно замостить прямоугольник 2 × n триоминошками? Триомино - это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

prb236

Например, замостить прямоугольник 2 × 3 можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю 10^6.

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

Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждая из следующих t строк содержит значение n (0 < n < 10^9).

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

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник 2 × n. Результат следует выводить по модулю 10^6.

Пример

Входные данные #1
3
3
4
6
Выходные данные #1
3
0
11