По заданному целому n вычислить количество способов, которыми можно разбить прямоугольник 4 × n плитками 3 × 1.
Поскольку ответ может быть большим, выведите остаток от деления результата на 1000000007.
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждый тест представляет собой одну строку, содержащую одно целое число n (1 ≤ n ≤ 10000).
Для каждого теста вывести в отдельной строке ответ по модулю 1000000007.