CF1174E.Ehab and the Expected GCD Problem

Let's define a function $f(p)$ on a permutation $p$ as follows. Let $g_i$ be the greatest common divisor (GCD) of elements $p_1$, $p_2$, ..., $p_i$ (in other words, it is the GCD of the prefix of length $i$). Then $f(p)$ is the number of distinct elements among $g_1$, $g_2$, ..., $g_n$.

Let $f_{max}(n)$ be the maximum value of $f(p)$ among all permutations $p$ of integers $1$, $2$, ..., $n$.

Given an integers $n$, count the number of permutations $p$ of integers $1$, $2$, ..., $n$, such that $f(p)$ is equal to $f_{max}(n)$. Since the answer may be large, print the remainder of its division by $1000\,000\,007 = 10^9 + 7$.

我们定义排列 $p$ 上的函数 $f(p)$ 如下：令 $g_i$ 表示元素 $p_1, p_2, \dots, p_i$ 的最大公约数（GCD）（即长度为 $i$ 的前缀的 GCD）。那么 $f(p)$ 就是 $g_1, g_2, \dots, g_n$ 中不同元素的个数。

令 $f_{\max}(n)$ 表示在所有 $1, 2, \dots, n$ 的排列 $p$ 中，$f(p)$ 所能达到的最大值。

给定整数 $n$，请计算满足 $f(p) = f_{\max}(n)$ 的 $1, 2, \dots, n$ 的排列 $p$ 的个数。由于答案可能很大，请输出其对 $1000\,000\,007 = 10^9 + 7$ 取模的结果。

The only line contains the integer $n$ ($2 \le n \le 10^6$) — the length of the permutations.

唯一的一行包含一个整数 $n$（$2 \le n \le 10^6$）——排列的长度。

The only line should contain your answer modulo $10^9+7$.

唯一的一行应包含你的答案对 $10^9+7$ 取模的结果。

Consider the second example: these are the permutations of length $3$:

• $[1,2,3]$, $f(p)=1$.
• $[1,3,2]$, $f(p)=1$.
• $[2,1,3]$, $f(p)=2$.
• $[2,3,1]$, $f(p)=2$.
• $[3,1,2]$, $f(p)=2$.
• $[3,2,1]$, $f(p)=2$.

The maximum value $f_{max}(3) = 2$, and there are $4$ permutations $p$ such that $f(p)=2$.

考虑第二个例子：这些是长度为 $3$ 的排列：

• $[1,2,3]$，$f(p)=1$。
• $[1,3,2]$，$f(p)=1$。
• $[2,1,3]$，$f(p)=2$。
• $[2,3,1]$，$f(p)=2$。
• $[3,1,2]$，$f(p)=2$。
• $[3,2,1]$，$f(p)=2$。

最大值 $f_{max}(3) = 2$，且有 $4$ 个排列 $p$ 满足 $f(p)=2$。