Derangements: Count Permutations with No Fixed Points

In the Hat Check room of Prime City's Grand Ball, the Attendant must return hats to guests such that no one gets their own hat. The number of such arrangements is called a derangement ÔÇö a permutation where no element appears in its original position. "A derangement of n items is a permutation with no fixed points," the Attendant explains. "The formula is D(n) = (n-1) * (D(n-1) + D(n-2)), with D(0) = 1 and D(1) = 0. Alternatively, D(n) = n! * sum of (-1)^k / k! for k = 0 to n." Given n, compute the number of derangements of n items modulo 10^9 + 7. Constraints: 0 <= n <= 10^6 Input: 3 Output: 2 Input: 4 Output: 9