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.

class Solution {
public:
    int findDerangement(int n) {
        long dp1 = 0, dp2 = 1, res = n - 1, mod = 1e9 + 7;
        for(int i = 3; i <= n; i++, dp1 = dp2, dp2 = res) {
            res = (i - 1) * (dp2 + dp1) % mod;
        }
        return res;
    }
};