n guests each own an assigned seat numbered 1 to n. They reshuffle so that every guest ends up in some seat, but no guest sits in their own assigned seat. Count the number of such reshuffles (permutations with no fixed point).
Report the count modulo 1000000007. For n = 0 there is exactly one arrangement (the empty one).
A single line containing the integer n.
A single integer: the number of fixed-point-free permutations modulo 1000000007.
Example 1
Input
2
Expected
1
Explanation
The only reshuffle of two guests that moves both is swapping them, so the answer is 1.
Example 2
Input
4
Expected
9
Explanation
Of the 24 permutations of four items, exactly 9 leave no item in place.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →