Description

众所周知，幻变骚灵 xygg 喜欢找 $1$ 玩，一天 xygg 入手了一套卡牌数量为 $n$ 的卡组，卡牌编号为 $1,2,\cdots,n$。xygg 会不断进行如下操作：

1. 在卡组中随机抽一张卡，在纸上记下它的编号，然后放回原卡组并重新打乱。
2. 计算纸上所有数字的最大公约数。
3. 如果最大公约数等于 $1$ 就结束操作，否则回到第一步继续操作。

xygg 想知道他抽卡的期望次数对 $10^9+7$ 取模的结果。

Format

Input

一个正整数 $n (1 \leqslant n \leqslant 10^5)$。

Output

输出一个正整数，表示 xygg 抽卡的期望次数对 $10^9+7$ 取模的结果。

Samples

1

1