eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Алгебраическая работа команды

Алгебраическая работа команды

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
3
1
2
2171
Вихідні дані #1
0
1
6425
Джерело 2014 German Collegiate Programming Contest (GCPC), Травень 24, Задача A