QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 21405. Min_25 筛

Statistics

Source: Libre OJ 6053

某一天,你发现了一个神奇的函数$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)$。

Input

一行一个整数 $n$。

Output

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

Examples

Input 1

6

Output 1

16

Input 2

233333

Output 2

179004642

Input 3

9876543210

Output 3

895670833

Scoring

对于$30\%$的数据,$n \leq 100$。

对于$60\%$的数据,$n \leq 10^6$。

对于$100\%$的数据,$1 \leq n \leq 10^{10}$。