题目内容

对于一个排列 $p$，定义函数 $f(p)$ 如下：令 $g_i$ 为元素 $p_1, p_2, \dots, p_i$ 的最大公约数（即前缀 $\gcd$）。则 $f(p)$ 是 $g_1, g_2, \dots, g_n$ 中互不相同的元素个数。

设 $f_{max}(n)$ 为所有 $1,2,\dots,n$ 的排列 $p$ 中 $f(p)$ 的最大值。

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

输入

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

输出

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

样例

样例 1

2

1

样例 2

3

4

样例 3

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$。

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