[AdditionalFile6053.zip](file://AdditionalFile6053.zip?type=additional_file)

#6053. 简单的函数

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

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

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

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

由于这个数比较大，你只需要输出 $\sum\limits_{i=1}^n f(i) \bmod (10^9+7)$。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数 $\sum\limits_{i=1}^n f(i) \bmod 1000000007$。

样例 1

输入

6

输出

16

样例 2

输入

233333

输出

179004642

样例 3

输入

9876543210

输出

895670833

数据范围与提示

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