Problem Description

While studying combinatorics, Xiao Lan proposed the concept of a "balanced position".

For a permutation $a_1, a_2, \ldots, a_n$ of $1$ to $n$, if position $i$ satisfies the following condition, then position $i$ is called a balanced position:

• The "number of elements on the left of position $i$ whose values are less than $a_i$" is exactly equal to the "number of elements on the right of position $i$ whose values are greater than $a_i$".

Here, the left side of position $i$ refers to positions $1, 2, \ldots, i-1$, and the right side refers to positions $i+1, i+2, \ldots, n$. Neither side includes position $i$ itself.

Xiao Lan believes that if a permutation has at least $\lceil n/2 \rceil$ balanced positions (where $\lceil x \rceil$ denotes the ceiling function), then this permutation is called a "good permutation".

Now, given the number $n$, please compute the number of good permutations among all permutations of $1$ to $n$. Since the answer may be very large, output it modulo $10^9 + 7$.

Input Format

Input one line containing one positive integer $n$.

Output Format

Output one line containing one integer, representing the number of good permutations modulo $10^9 + 7$.

4

7

Hint

Sample Explanation

When $n = 4$, a good permutation needs at least $\lceil 4/2 \rceil = 2$ balanced positions.

Take the permutation $4\ 3\ 2\ 1$ as an example: on the left of every position, there is no number smaller than the element at the current position, and on the right there is also no number greater than the element at the current position. Therefore, all four positions are balanced positions. This permutation is a good permutation.

Among all permutations of length $4$, there are $7$ good permutations in total, so the output is $7$.

Constraints

For $30\%$ of the testdata, $1 \le n \le 10$.

For $60\%$ of the testdata, $1 \le n \le 5000$.

For all testdata, $1 \le n \le 10^7$.

Translated by ChatGPT 5