markdown E. Ehab 与期望的 GCD 问题
每个测试的时间限制：$2$ 秒
每个测试的内存限制：$256$ MB
输入：标准输入
输出：标准输出

我们定义一个函数 $f(p)$，其中 $p$ 是一个排列。令 $g_i$ 为前 $i$ 个元素（即长度为 $i$ 的前缀）的最大公约数（GCD）。那么 $f(p)$ 的值是 $g_1, g_2, \dots, g_n$ 中不同元素的个数。

定义 $\text{max}(n)$ 为在所有由整数 $1, 2, \dots, n$ 构成的排列 $p$ 中，$f(p)$ 可能取到的最大值。

给定一个整数 $n$，请计算有多少个由 $1, 2, \dots, n$ 构成的排列 $p$，使得 $f(p)$ 等于 $\text{max}(n)$。由于答案可能很大，请输出其对 $1\,000\,000\,007 = 10^9 + 7$ 取模的结果。

输入
仅一行，包含一个整数 $n$（$1 \le n \le 10^6$）—— 排列的长度。

输出
仅一行，输出答案对 $10^9 + 7$ 取模的结果。

输入样例

2

输出样例

1

输入样例

3

输出样例

4

输入样例

6

输出样例

120

说明
考虑第二个样例：长度为 $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$

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