#6053. 简单的函数

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: fjzzq2002

题目描述

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

  1. f(1)=1f(1)=1f(1)=1
  2. f(pc)=p⊕cf(p^c)=p \oplus cf(pc)=pcppp 为质数,⊕\oplus 表示异或)。
  3. f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b)aaabbb 互质)。

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

由于这个数比较大,你只需要输出 ni=1f(i)mod(109+7)

输入格式

一行一个整数 nnn

输出格式

一行一个整数 ni=1f(i)mod1000000007

样例

样例输入 1

6

样例输出 1

16

样例输入 2

233333

样例输出 2

179004642

样例输入3

9876543210

样例输出3

895670833

数据范围与提示

对于30%30\%30%的数据,n≤100n \leq 100n100
对于60%60\%60%的数据,n≤106n \leq 10^6n106
对于100%100\%100%的数据,1≤n≤10101 \leq n \leq 10^{10}1n1010