走向一

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

初始时有一个空数组 $a$ 和一个整数 $m$。反复执行以下操作：

1. 从 $1$ 到 $m$ 中等概率、相互独立地随机选择一个整数，并把它添加到数组末尾；
2. 如果数组中所有元素的最大公约数等于 $1$，则停止；否则继续操作。

求停止时数组长度的期望。该期望可写成最简分数 $P/Q$，且 $Q\not\equiv0\pmod {10^9+7}$。输出 $P\cdot Q^{-1}\bmod(10^9+7)$。

输入格式

一行一个整数 $m$。

输出格式

输出期望长度对 $10^9+7$ 取模的结果。

样例输入 1

1

样例输出 1

1

样例输入 2

2

样例输出 2

2

数据范围

$1\le m\le100000$。