Алгебраическая работа команды
Знаменитые пионеры теории групп и линейной алгебры хотят объединиться и скооперировать свои теории. В теории групп перестановки – известные также как биективные функции – играют важную роль. Для конечного множества A, функция σ : A → A называется перестановкой A если существует такая функция ρ : A → A что
σ(ρ(a)) = a и ρ(σ(a)) = a для всех a из A
Вторая часть новой команды - эксперты линейной алгебры - имеют дело с идемпотентными функциями. Они появляются при вычислении теней в 3D играх или при вычислении например транзитивных замыканий. Функция p : A → A называется идемпотентной если только
ρ(ρ(a)) = ρ(a) для всех a из A
Для продолжения исследования им нужна Ваша помощь. Команду интересуют неидемпотентные перестановки для заданного конечного множества A. Сначала они обнаружили, что результат зависит от размера множества. Для заданного размера n (1 ≤ n ≤ 10^5) Вам следует найти количество неидемпотентных перестановок для множества размера n.
Входные данные
Начинаются с количества тестов t (t ≤ 100). Далее следуют t строк, каждая из которых содержит размер множества n (1 ≤ n ≤ 10^5).
Выходные данные
Для каждого теста вывести в отдельной строке количество неидемпотентных функций мощности n по модулю 1 000 000 007 = (10^9 + 7).