A derangement is a permutation of the numbers 1 to n where no value stays in its original position (i.e., for every position i, the value i is not placed at index i). Given an integer n, return the number of such permutations, with the result taken modulo 1,000,000,007.
Example 1:
n = 4
result = 9
Explanation: For [1, 2, 3, 4], none of the 9 valid permutations keep any element at its original index. Some examples: [2, 1, 4, 3], [2, 3, 4, 1], [3, 4, 1, 2].
Example 2:
n = 1
result = 0
Example 3:
n = 2
result = 1
Explanation: The only derangement is [2, 1].
Example 4:
n = 0
result = 1
Explanation: The empty permutation is considered one valid way.
Sample usage (Java-style):
class Derangement {
public int countNoFixed(int n) { /* ... */ }
}
Derangement d = new Derangement();
d.countNoFixed(4) -> 9
d.countNoFixed(5) -> 44
0 ≤ n ≤ 2,000,000 Return the count modulo 1,000,000,007