e-olymp
Задачи

Триомино

Триомино

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

prb236

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
3
4
6
Выходные данные #1
3
0
11