问题重述

给定 $n$，定义排列 $p$ 的前缀 $\gcd$ 序列 $g_i = \gcd(p_1, \dots, p_i)$，$f(p)$ 为 $g_1,\dots,g_n$ 中不同值的个数。设 $f_{\max}(n)$ 为所有排列中 $f(p)$ 的最大值。求有多少个排列 $p$ 使得 $f(p) = f_{\max}(n)$，答案对 $10^9+7$ 取模。

第一步：确定 $f_{\max}(n)$ 及第一个数的形式

前缀 $\gcd$ 序列是单调不增的（每次加入新数，$\gcd$ 可能变小或不变）。设 $g_1 = x$，则每次 $\gcd$ 变化时，其质因数分解中的总指数和至少减少 $1$。因此 $f(p)$ 不超过 $x$ 的质因数总指数和。为了最大化这个值，我们希望 $x$ 的指数和最大，同时 $x \le n$。

最小质因数是 $2$，所以形如 $2^a$ 的数有 $a$ 个指数。但是 $2^{a-1} \cdot 3$ 的指数和也是 $(a-1)+1 = a$，且数值可能 $\le n$（如果 $2^{a-1}\cdot 3 \le n$），所以也是候选。更大的质数（如 $5$）会降低指数和（因为 $2^2=4$ 比 $5$ 小，指数更多）。因此：

• 设 $a = \lfloor \log_2 n \rfloor$，即 $2^a \le n < 2^{a+1}$。
• 第一个数只能是 $2^a$ 或（若 $2^{a-1}\cdot 3 \le n$）$2^{a-1}\cdot 3$。
• $f_{\max}(n) = a$。

第二步：动态规划状态设计

由于 $\gcd$ 只能从 $2^a$ 或 $2^{a-1}\cdot 3$ 开始，每次减少一个 $2$ 或一个 $3$（$3$ 最多出现一次），最终变成 $1$。因此 $\gcd$ 始终形如 $2^j \cdot 3^k$，其中 $k \in \{0,1\}$，$0 \le j \le a$。

定义 $dp[i][j][k]$ 表示已经填了前 $i$ 个数，且当前前缀 $\gcd = 2^j \cdot 3^k$ 的方案数。使用滚动数组优化空间。

第三步：转移方程

设 $cnt[j][k] = \left\lfloor \frac{n}{2^j \cdot 3^k} \right\rfloor$（若 $2^j \cdot 3^k > n$ 则 $cnt=0$）。注意前 $i-1$ 个数一定都是 $2^j \cdot 3^k$ 的倍数，因为它们的前缀 $\gcd$ 是它的倍数。

当前状态 $(j,k)$ 可能来自：

1. $\gcd$ 不变：前 $i-1$ 个数的 $\gcd$ 也是 $(j,k)$，第 $i$ 个数是 $2^j \cdot 3^k$ 的倍数。可选数个数为 $cnt[j][k] - (i-1)$（已经用掉了 $i-1$ 个倍数）。

   $$dp[i][j][k] \mathrel{+}= dp[i-1][j][k] \times \bigl(cnt[j][k] - (i-1)\bigr) $$

2. 减少一个 $2$：前 $i-1$ 个数的 $\gcd$ 为 $(j+1, k)$，第 $i$ 个数是 $2^j \cdot 3^k$ 的倍数，但不是 $2^{j+1} \cdot 3^k$ 的倍数。可选数个数为 $cnt[j][k] - cnt[j+1][k]$。

   $$dp[i][j][k] \mathrel{+}= dp[i-1][j+1][k] \times \bigl(cnt[j][k] - cnt[j+1][k]\bigr) $$

3. 减少一个 $3$（仅当 $k=0$ 时可能，从 $(j,1)$ 转移）：前 $i-1$ 个数的 $\gcd$ 为 $(j,1)$，第 $i$ 个数是 $2^j$ 的倍数，但不是 $2^j \cdot 3$ 的倍数。可选数个数为 $cnt[j][0] - cnt[j][1]$。

   $$dp[i][j][0] \mathrel{+}= dp[i-1][j][1] \times \bigl(cnt[j][0] - cnt[j][1]\bigr) $$

注意：对于 $k=1$，不存在减少一个 $3$ 的情况（因为 $3$ 的指数最多为 $1$，减少后 $k=0$ 已经在上一条处理了）。

第四步：初始化和答案

• 第一个数有两种可能：
  • $dp[1][a][0] = 1$（第一个数取 $2^a$）；
  • 如果 $2^{a-1} \cdot 3 \le n$，则 $dp[1][a-1][1] = 1$。
• 最终答案：填完 $n$ 个数后，$\gcd$ 必须为 $1$，即 $j=0,k=0$，所以答案为 $dp[n][0][0]$。

第五步：复杂度分析

• $a \approx \log_2 n \le 20$，状态数 $O(n \cdot \log n \cdot 2)$。
• 使用滚动数组，空间 $O(\log n)$。
• 每个状态转移 $O(1)$，总时间复杂度 $O(n \log n)$，对于 $n \le 10^6$ 完全可行。

第六步：代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;

int n;
int dp[2][21][2];  // 滚动数组：当前/上一行，j是2的指数，k是3的指数（0或1）
int cnt[21][2];    // cnt[j][k] = floor(n / (2^j * 3^k))

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // 预处理 cnt[j][k] 和 2 的幂
    int maxp = 0;
    while ((1 << (maxp + 1)) <= n) ++maxp;  // 最大指数

    for (int j = 0; j <= maxp; ++j) {
        cnt[j][0] = n / (1 << j);
        if ((1 << j) * 3 <= n) {
            cnt[j][1] = n / ((1 << j) * 3);
        } else {
            cnt[j][1] = 0;
        }
    }

    // 初始化：第一个位置
    dp[1][maxp][0] = 1;                       // 第一个数是 2^maxp
    if (maxp >= 1 && (1 << (maxp - 1)) * 3 <= n) {
        dp[1][maxp - 1][1] = 1;               // 第一个数是 2^(maxp-1) * 3
    }

    int cur = 1, lst = 0;
    for (int i = 2; i <= n; ++i) {
        swap(cur, lst);
        // 清零当前层
        for (int j = 0; j <= maxp; ++j) {
            dp[cur][j][0] = dp[cur][j][1] = 0;
        }

        for (int j = 0; j <= maxp; ++j) {
            // 处理 k = 0 (当前 gcd = 2^j)
            if (dp[lst][j][0]) {
                // 1) gcd 不变：下一个数必须是 2^j 的倍数，但不能是 2^(j+1) 的倍数？不对，只要它是 2^j 的倍数，gcd 就不会变小。
                //    实际上，如果下一个数是 2^j 的倍数，gcd 至少是 2^j，但可能变成 2^(j+1) 的因子？不会，因为当前 gcd 已经是 2^j，加入一个倍数，新 gcd 仍然是 2^j 的倍数，但不一定比 2^j 大。
                //    然而，我们想要 gcd 保持不变，即新数必须是 2^j 的倍数，并且不能是 2^(j+1) 的倍数？不对，如果它是 2^(j+1) 的倍数，那么新 gcd 至少是 2^(j+1)，但当前 gcd 是 2^j，所以新 gcd 实际上会变成 2^(j+1)？这不可能，因为当前 gcd 已经是 2^j，而新数是 2^(j+1) 的倍数，那么 gcd 会变成 2^(j+1) 吗？不，当前数的 gcd 是 2^j，新数是 2^(j+1) 的倍数，但 gcd(2^j, 2^(j+1)*x) = 2^j，因为 2^j 能整除 2^(j+1)*x，但反过来不行。所以实际上，gcd 保持不变的条件是：新数是当前 gcd 的倍数即可，因为 gcd 不会变大。
                //    因此，gcd 不变时，可选数个数 = cnt[j][0] - (i-1) ？但是要注意：之前已经用掉的 i-1 个数中，有些可能不是 2^j 的倍数？不对，之前 i-1 个数的 gcd 是 2^j，所以它们都是 2^j 的倍数。所以已经用掉的 i-1 个数全部包含在 cnt[j][0] 中。
                //    所以可选数个数 = cnt[j][0] - (i-1)
                dp[cur][j][0] = (dp[cur][j][0] + 1LL * dp[lst][j][0] * (cnt[j][0] - (i - 1))) % MOD;
            }

            // 2) 减少一个2：从 j+1 转移过来，新数必须是 2^j 的倍数，但不能是 2^(j+1) 的倍数（否则 gcd 不变或变大？变大不可能）
            if (j + 1 <= maxp && dp[lst][j + 1][0]) {
                // 可选数个数 = 2^j 的倍数个数 - 2^(j+1) 的倍数个数 = cnt[j][0] - cnt[j+1][0]
                dp[cur][j][0] = (dp[cur][j][0] + 1LL * dp[lst][j + 1][0] * (cnt[j][0] - cnt[j + 1][0])) % MOD;
            }

            // 3) 减少一个3：从 (j,1) 转移过来，新数必须是 2^j 的倍数，但不能是 2^j * 3 的倍数（否则 gcd 仍含3）
            if (dp[lst][j][1]) {
                // 可选数个数 = 2^j 的倍数个数 - 2^j * 3 的倍数个数 = cnt[j][0] - cnt[j][1]
                dp[cur][j][0] = (dp[cur][j][0] + 1LL * dp[lst][j][1] * (cnt[j][0] - cnt[j][1])) % MOD;
            }

            // 处理 k = 1 (当前 gcd = 2^j * 3)
            if (cnt[j][1] == 0) continue;  // 不存在这种 gcd
            if (dp[lst][j][1]) {
                // 1) gcd 不变：下一个数必须是 2^j * 3 的倍数
                dp[cur][j][1] = (dp[cur][j][1] + 1LL * dp[lst][j][1] * (cnt[j][1] - (i - 1))) % MOD;
            }
            // 2) 减少一个2：从 (j+1,1) 转移过来
            if (j + 1 <= maxp && dp[lst][j + 1][1]) {
                // 可选数个数 = 2^j * 3 的倍数个数 - 2^(j+1) * 3 的倍数个数 = cnt[j][1] - cnt[j+1][1]
                dp[cur][j][1] = (dp[cur][j][1] + 1LL * dp[lst][j + 1][1] * (cnt[j][1] - cnt[j + 1][1])) % MOD;
            }
            // 注意：减少一个3 的情况不存在，因为 k=1 时，3的指数为1，减少3后变为 (j,0)，这属于转移到 k=0，已经在上面的 k=0 情况中处理了（从 (j,1) 到 (j,0)）。
        }
    }

    // 最终答案：填完所有数后，gcd 必须为 1，即 j=0, k=0
    cout << (dp[cur][0][0] + MOD) % MOD << '\n';
    return 0;
}