Триміно#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.
Приклад 1