Permutation with Forbidden Adjacencies

A secret divine instruction is given as a string \(s_1\) composed of lowercase letters. In order not to reveal the secret relationships between consecutive characters in \(s_1\), the instruction is recorded as another string \(s_2\) (also consisting of lowercase letters) with the following restriction:

For every two adjacent letters in \(s_1\), that ordered pair must not appear as two adjacent letters (in the same order) anywhere in \(s_2\>.

In this problem, assume that \(s_1\) is a string of distinct letters of length \(n\). Thus, \(s_2\) is a permutation of the characters of \(s_1\) (so its length is also \(n\)). The forbidden adjacent pairs are exactly \((s_{1,1}, s_{1,2}), (s_{1,2}, s_{1,3}), \dots, (s_{1,n-1}, s_{1,n})\).

Your task is to count the number of permutations \(s_2\) of \(s_1\) that avoid having any of these forbidden pairs as consecutive characters. Since the answer can be large, output it modulo \(10^9+7\).

Mathematical Formulation

The total number of permutations of \(n\) distinct items is \(n!\). Using the inclusion–exclusion principle we can count the number of valid permutations as:

[ \text{Answer} = \sum_{k=0}^{n-1} (-1)^k \cdot \binom{n-1}{k} \cdot (n-k)!,. ]

inputFormat

The input consists of a single integer \(n\) representing the length of the divine instruction \(s_1\) (and hence the length of \(s_2\)).

\(1 \le n \le 10^6\) (for example).

outputFormat

Output a single integer which is the number of valid permutations \(s_2\) modulo \(10^9+7\).

sample

1

1