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