1184: #6053. 简单的函数

某一天，你发现了一个神奇的函数$f(x)$，它满足很多神奇的性质：

1. $f(1)=1$。
2. f(pc)=p⊕cf(p^c)=p \oplus cf(p​c​​)=p⊕c（$p$ 为质数，$\oplus$ 表示异或）。
3. $f(ab)=f(a)f(b)$（$a$ 与 $b$ 互质）。

你看到这个函数之后十分高兴，于是就想要求出 ∑i=1nf(i)\sum\limits_{i=1}^n f(i)​i=1​∑​n​​f(i)。

由于这个数比较大，你只需要输出 $\sum _{i=1}^{n}f\left(i\right)mod1000000007$。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数 $\sum _{i=1}^{n}f\left(i\right)mod1000000007$。

样例

样例输入 1

6

样例输出 1

16

样例输入 2

233333

样例输出 2

179004642

样例输入3

9876543210

样例输出3

895670833

数据范围与提示

对于$30\%$的数据，$n\le 100$。
对于$60\%$的数据，n≤106n \leq 10^6n≤10​6​​。
对于$100\%$的数据，1≤n≤10101 \leq n \leq 10^{10}1≤n≤10​10​​。