← 返回题目列表

Codeforces · 1139/D

D. 步骤一

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

Vivek 最初有一个空数组 $$$a$$$ 和一些整数常量 $$$m$$$。

他执行以下算法:

1. 在$$$1$$$到$$$m$$$范围内统一选择一个随机整数$$$x$$$,将其附加到$$$a$$$的末尾。
2. 计算 $$$a$$$ 中整数的最大公约数。
3. 如果等于$$$1$$$,则中断
4. 否则,返回步骤$$$1$$$。

求 $$$a$$$ 的预期长度。可以证明,它可以表示为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是互质整数,$$$Q\neq 0 \pmod{10^9+7}$$$。打印 $$$P \cdot Q^{-1} \pmod{10^9+7}$$$ 的值。

输入

第一行也是唯一一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 100000$$$)。

输出

打印单个整数 - 数组 $$$a$$$ 的预期长度,写为 $$$P \cdot Q^{-1} \pmod{10^9+7}$$$。

示例

输入 #1

1

输出 #1

1

输入 #2

2

输出 #2

2

输入 #3

4

输出 #3

333333338

注意

在第一个示例中,由于 Vivek 只能选择 $$$1$$$ 到 $$$1$$$ 之间的整数,因此他在第一次追加操作后将得到 $$$a=[1]$$$,然后退出算法。因此 $$$a$$$ 的长度始终为 $$$1$$$,因此其期望值也是 $$$1$$$。

在第二个示例中,Vivek 每次都会附加 $$$1$$$ 或 $$$2$$$,因此在完成算法后,他最终会得到一定数量的 $$$2$$$(可能为零),最后只有一个 $$$1$$$。列表的预期长度为 $$$1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$$$。