Колобки против Энигмы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иностранный торговец животными Карбофос успел найти покупателя похищенного полосатого слона. Он отправил ему в Германию шифрованное сообщение.

В тот же день братьям детективам доложили о пропаже из столичного музея шифровальной машины «Энигма 43». Шеф уверен, что это не совпадение.

«Энигма 43» всегда генерирует целое число $$$\overline{a_1a_2\ldots a_n}$$$ ($$$0 \le a_i \le 9$$$, $$$a_1 \neq 0$$$) длины $$$n$$$, обладающее особым свойством: ни у каких двух соседних пар цифр не совпадает НОД (наибольший общий делитель). Другими словами, для любой тройки подряд идущих цифр $$$\overline{a_i a_{i+1} a_{i+2}}$$$ верно, что $$$\gcd(a_i, a_{i+1}) \neq \gcd(a_{i+1}, a_{i+2})$$$. Любое число, обладающее таким свойством, может быть сгенерировано. В этой задаче $$$\gcd(0, 0) = 0$$$.

В сообщении могут содержаться важные для следствия данные, но его проблематично восстановить. Коллега предложил воспользоваться полным перебором.

Помогите братьям Колобкам посчитать количество сообщений, которые Карбофос мог отправить с помощью «Энигма 43». Так как ответ может быть большим, посчитайте его по модулю $$$10^9 + 7$$$.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

В единственной строке каждого набора дано целое число $$$n$$$ ($$$2 \le n \le 10^{18}$$$) — длина сообщения.

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

Для каждого набора данных выведите единственное число — количество чисел длины $$$n$$$, которые могли быть сгенерированы Энигмой по модулю $$$10^9 + 7$$$.

Пример

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

    6234567

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

    9044326631360172811389296

Примечание

Для $$$n=3$$$ некоторые числа, которые могли быть сгенерированы Энигмой: $$$124$$$, $$$322$$$, $$$504$$$, $$$661$$$, $$$993$$$