CF1174E Ehab and the Expected GCD Problem

我们定义一个函数 $f(p)$，作用于一个排列 $p$。令 $g_i$ 表示 $p_1, p_2, \ldots, p_i$ 的最大公约数（即长度为 $i$ 的前缀的最大公约数）。那么 $f(p)$ 就是 $g_1, g_2, \ldots, g_n$ 中不同元素的个数。 令 $f_{max}(n)$ 表示所有 $1, 2, \ldots, n$ 的排列 $p$ 中 $f(p)$ 的最大值。 给定整数 $n$，请计算有多少个排列 $p$ 满足 $f(p) = f_{max}(n)$。由于答案可能很大，请输出其对 $1000000007 = 10^9 + 7$ 取模的结果。

一行一个整数 $n$（$2 \le n \le 10^6$），表示排列的长度。

输出一行，表示满足条件的排列个数对 $10^9+7$ 取模后的结果。

以第二个样例为例，长度为 $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$，满足 $f(p)=2$ 的排列有 $4$ 个。 由 ChatGPT 4.1 翻译