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
n in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo
109 + 7.
Input: n = 3 Output: 2 Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
Input: n = 2 Output: 1
1 <= n <= 106