Lucky Permutations

Given a positive integer n, count the number of lucky permutations of an array of size n. A permutation of the integers from 1 to n is considered lucky if no element appears in its original position (i.e. there is no fixed point). Such permutations are also known as derangements.

The number of derangements, denoted by \(D(n)\), can be computed using the recurrence relation:

\[ D(n) = (n-1)\,(D(n-1) + D(n-2)),\quad \text{with } D(1)=0 \text{ and } D(2)=1. \]

Given \(n\), output the value of \(D(n) \bmod 10^9+7\).

inputFormat

The input consists of a single integer n (where n ≥ 1) given via stdin.

outputFormat

Output one integer on stdout, the number of lucky permutations (derangements) of the array modulo \(10^9+7\).

1

0