Читати знову?

Для заданого цілого числа n потрібно обчислити кількість способів, якими можна заповнити прямокутник розміром 4 × n плитками розміром 3 × 1.

Оскільки результат може бути дуже великим, виведіть залишок від ділення цього результату на 1000000007.

Вхідні дані

Перша строка містить кількість тестів t (1 ≤ t ≤ 100). Кожен тест представлений однією строкою, що містить одне ціле число n (1 ≤ n ≤ 10000).

Вихідні дані

Для кожного тесту виведіть відповідь у окремому рядку, взяту за модулем 1000000007.

Приклади