Знаменитые пионеры теории групп и линейной алгебры хотят объединиться и скооперировать свои теории. В теории групп перестановки – известные также как биективные функции – играют важную роль. Для конечного множества A, функция σ : A → A называется перестановкой A если существует такая функция ρ : A → A что

σ(ρ(a)) = a and ρ(σ(a)) = a for all a from A

Вторая часть новой команды - эксперты линейной алгебры - имеют дело с идемпотентными функциями. Они появляются при вычислении теней в 3D играх или при вычислении например транзитивных замыканий. Функция p : A → A называется идемпотентной если только

ρ(ρ(a)) = ρ(a) для всех a из A

Для продолжения исследования им нужна Ваша помощь. Команду интересуют неидемпотентные перестановки для заданного конечного множества A. Сначала они обнаружили, что результат зависит от размера множества. Для заданного размера n (1 ≤ n ≤ 105) Вам следует найти количество неидемпотентных перестановок для множества размера n.

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

Начинаются с количества тестов t (t ≤ 100). Далее следуют t строк, каждая из которых содержит размер множества n (1 ≤ n ≤ 105).

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

Для каждого теста вывести в отдельной строке количество неидемпотентных функций мощности n по модулю 1 000 000 007 = (109 + 7).