Триомино#236
Сколькими способами можно замостить прямоугольник 2 \times n триомино? Триомино — это геометрическая фигура, составленная из трёх 1 \times 1 квадратов, соединённых по полным рёбрам. Существует ровно два возможных триомино:
Например, прямоугольник 2 \times 3 можно замостить ровно различными способами.
Поскольку ответ может быть большим, выведите количество способов по модулю 10^6.
Первая строка содержит количество тестовых случаев (1 \le t \le 100). Каждая из следующих строк содержит целое число (0 < n < 10^9).
Для каждого теста в отдельной строке выведите число способов замостить прямоугольник 2 \times n. Ответ выведите по модулю 10^6.
Example 1