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

Поскольку ответ может быть большим, выведите остаток от деления результата на 1000000007.

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

Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждый тест представляет собой одну строку, содержащую одно целое число n (1 ≤ n ≤ 10000).

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

Для каждого теста вывести в отдельной строке ответ по модулю 1000000007.