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

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

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

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

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

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

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

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

Пример входа	Пример выхода
3 1 2 2171	0 1 6425

РЕШЕНИЕ

математика

Анализ алгоритма

Единственной идемпотентной перестановкой является тождественная. Поэтому количество неидемпотентных функций мощности n равно n! – 1.

Реализация алгоритма

Объявим рабочие константы и массив f, где f[i] = i! mod (10⁹ + 7).

#define MOD 1000000007

#define MAX 100010

long long f[MAX];

Заполняем массив f факториалами чисел.

f[0] = 1;

for(i = 1; i < MAX; i++)

f[i] = (f[i-1] * i) % MOD;

Читаем входные данные и выводим ответ.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

printf("%lld\n",f[n] - 1);

}