# 634. Find the Derangement of An Array

## Description

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

## Solutions

• class Solution {
public int findDerangement(int n) {
final int mod = (int) 1e9 + 7;
long a = 1, b = 0;
for (int i = 2; i <= n; ++i) {
long c = (i - 1) * (a + b) % mod;
a = b;
b = c;
}
return (int) b;
}
}

• class Solution {
public:
int findDerangement(int n) {
long long a = 1, b = 0;
const int mod = 1e9 + 7;
for (int i = 2; i <= n; ++i) {
long long c = (i - 1) * (a + b) % mod;
a = b;
b = c;
}
return b;
}
};

• class Solution:
def findDerangement(self, n: int) -> int:
mod = 10**9 + 7
a, b = 1, 0
for i in range(2, n + 1):
a, b = b, ((i - 1) * (a + b)) % mod
return b


• func findDerangement(n int) int {
a, b := 1, 0
const mod = 1e9 + 7
for i := 2; i <= n; i++ {
a, b = b, (i-1)*(a+b)%mod
}
return b
}