Permutations with Restricted Modular Condition

Given an integer n, consider all permutations p = [p₁, p₂, …, p_n] of the numbers 1 to n. We define p_n+1 = p₁ (i.e. the permutation is considered circular). A permutation is called valid if for every index i (1 ≤ i ≤ n), the condition

\( p_i \bmod p_{i+1} \le 2 \)

holds. Here, the \( \bmod \) operation is the standard remainder operation and all comparisons and computations are done with integers. Output the total number of valid permutations modulo \(10^9+7\).

Note: In a circular sequence, if p_i < p_i+1, then since p_i mod p_i+1 = p_i, we must have p_i \le 2. For indices where p_i \ge p_{i+1}, the condition \(p_i \bmod p_{i+1} \le 2\) must also be verified. It can be shown that for n = 1 the answer is 1, for n = 2 the answer is 2, and for all n \ge 3 the answer equals \(3 \times (n-1)!\) modulo \(10^9+7\).

inputFormat

The input consists of a single line containing an integer n (1 ≤ n).

outputFormat

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

sample

1

1