← 返回题目列表

Codeforces · 1174/E

E. Ehab 和预期的 GCD 问题

中文机器翻译题面 查看原题

让我们在排列 $$$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$$$。