I. Переполох в НИИЧАВО
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Однажды одному известному программисту из Научно-Исследовательского Института Чародейства и Волшебства Александру Привалову стало скучно, и он решил устроить переполох. Александр не смог придумать ничего лучше, чем решить какую-нибудь нерешённую проблему из книги Януса Полуэктовича Невструева «Уравнения математической магии». В качестве проблемы он решил изучить свойства следующей функции: f(a) = 1a·2a - 1·3a - 2·...·(a - 1)2·a1, при этом f(0) = 1. Для этого ему надо найти значения этой функции в нескольких точках по модулю 109 + 7. Помогите Александру устроить переполох.

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

В первой строке входных данных вам дано единственное целое число n (1 ≤ n ≤ 105) — количество запросов. В следующих n строках следуют запросы. Каждый запрос представляет из себя единственное число ai (0 ≤ ai ≤ 105).

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

Выведите n строк, в i-й строчке следует вывести ответ на запрос — значение функции f(ai) по модулю 109 + 7.

Пример
Входные данные
3
3
4
5
Выходные данные
12
288
34560