Count the Derangements

Difficulty: 1600 3000 ms 128 MB

math combinatorics

A derangement is a permutation with no fixed point (no element stays in its own position). Count the derangements of N items modulo 10⁹+7.

Input: one integer N.

Output: D_N mod 10⁹+7.

Constraints:

• 0 ≤ N ≤ 10⁶

Sample Tests

3

2

1

0

Read the Editorial