At a party n guests each brought one gift, and the gifts are redistributed so that every guest receives exactly one gift and nobody receives the gift they brought. Count the number of valid redistributions. Report the count modulo 1000000007.
A single line with one integer n.
A single integer: the number of redistributions with no self-match, modulo 1000000007.
Example 1
Input
4
Expected
9
Explanation
There are 9 derangements of 4 items, so the answer is 9.
Example 2
Input
0
Expected
1
Explanation
With no guests there is exactly one (empty) redistribution, D(0)=1.
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 →