让我们在排列 $$$p$$$ 上定义一个函数 $$$f(p)$$$,如下所示。设$$$g_i$$$为元素$$$p_1$$$、$$$p_2$$$、...、$$$p_i$$$的最大公约数(GCD)(换句话说,它是长度为$$$i$$$的前缀的GCD)。那么 $$$f(p)$$$ 是 $$$g_1$$$, $$$g_2$$$, ..., $$$g_n$$$ 之间不同元素的数量。
设 $$$f_{max}(n)$$$ 为整数 $$$1$$$、$$$2$$$、...、$$$n$$$ 的所有排列 $$$p$$$ 中 $$$f(p)$$$ 的最大值。
给定一个整数$$$n$$$,计算整数$$$1$$$、$$$2$$$、...、$$$n$$$的排列数$$$p$$$,使得$$$f(p)$$$等于$$$f_{max}(n)$$$。由于答案可能很大,因此打印除以 $$$1000\,000\,007 = 10^9 + 7$$$ 的余数。
输入
唯一一行包含整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) — 排列的长度。
输出
唯一的一行应包含您的答案模 $$$10^9+7$$$。
示例
输入 #1
2
输出 #1
1
输入 #2
3
输出 #2
4
输入 #3
6
输出 #3
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$$$排列$$$p$$$使得$$$f(p)=2$$$。