#6053. 简单的函数
题目描述
某一天，你发现了一个神奇的函数f(x)f(x)f(x)，它满足很多神奇的性质：
- f(1)=1f(1)=1f(1)=1。
- f(pc)=p⊕cf(p^c)=p \oplus cf(pc)=p⊕c（ppp 为质数，⊕\oplus⊕ 表示异或）。
- f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b)（aaa 与 bbb 互质）。
你看到这个函数之后十分高兴，于是就想要求出 ∑i=1nf(i)\sum\limits_{i=1}^n f(i)i=1∑nf(i)。
由于这个数比较大，你只需要输出 n∑i=1f(i)mod1000000007。
输入格式
一行一个整数 nnn。
输出格式
一行一个整数 n∑i=1f(i)mod1000000007。
样例
样例输入 1
6样例输出 1
16样例输入 2
233333样例输出 2
179004642样例输入3
9876543210样例输出3
895670833数据范围与提示
对于30%30\%30%的数据，n≤100n \leq 100n≤100。
对于60%60\%60%的数据，n≤106n \leq 10^6n≤106。
对于100%100\%100%的数据，1≤n≤10101 \leq n \leq 10^{10}1≤n≤1010。