Book Exchange — Derangement Count
H · hardP · Verified PYQmath
Problem
A teacher distributes N books to N students and wants to exchange them weekly so every student gets a different book (not their own). Find the total number of valid exchanges (derangements) modulo 10^7+7. Example: N=4 → 9 valid exchanges (no student gets their original book).
Constraints
1 <= N <= 1000000
Example
Input
4
Output
9
Derangement recurrence: D(n) = (n-1) \* (D(n-1) + D(n-2)). Base: D(1)=0, D(2)=1.