407373: GYM102775 I Переполох в НИИЧАВО

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

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

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

3
3
4
5

12
288
34560