Задача №113514. Неподвижные точки
Назовём неподвижной точкой перестановки такой индекс i , что a i = i . Посчитайте число перестановок длины n , в которых нет неподвижных точек. Так как это число может быть воистину огромным, выведите его по модулю 10 9 + 7 .
В единственной строке входного файла задано целое число n ( 1 ≤ n ≤ 10 7 ) — количество элементов в перестановке.
В единственной строке выведите количество перестановок из n элементов без неподвижных точек, взятое по модулю 10 9 + 7 .
n ≤ 10 — 30 баллов.
n ≤ 5000 — 40 баллов.
n ≤ 10 6 — 20 баллов.
n ≤ 10 5 — 10 баллов.
3
2