634 Find the Derangement of An Array

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

You are given an integer n. There is originally an array consisting of n integers from 1 to n in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo 109 + 7.

Example 1:

Input: n = 3
Output: 2
Explanation: The original array is [1,2,3].
The two derangements are [2,3,1] and [3,1,2].

Example 2:

Input: n = 2
Output: 1

Constraints:

• 1 <= n <= 106

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findDerangement(self, n: int) -> int:
        MOD = 10**9+7
        dp = [0, 1]
        if n <= 2:
            return dp[n - 1] 
        for i in range(3, n+1):
            j = (dp[0] + dp[1]) * (i - 1) % MOD
            dp[0] = dp[1]
            dp[1] = j
        return dp[-1]