Finally, for the "Secret Santa" example (nobody should draw their own name), Oindrila needs to count derangements of N people, modulo the prime. Given N, print the number of permutations of 1..N in which NO element appears in its original position (derangements), modulo 10^9+7. Derive and use the recurrence D(n) = (n-1)*(D(n-1)+D(n-2)) rather than brute-force generating permutations.
Input
One integer N.
Output
D(N) mod (10^9+7).
Constraints
0 ≤ N ≤ 10^6
Sample Input
4
Sample Output
9
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.