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

#6784. 简单的函数 10^12 版

标签: 传统 | 时间限制: 10000 ms | 内存限制: 512 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$ 互质）。

令 $S(m)=\sum\limits_{i=1}^m f(i) \bmod (10^9+7)$，你需要对于 $i=1,2,3,\cdots,n$ 求出 $S(\lfloor n/i\rfloor)$，去重并输出异或和。

输入格式

一行一个正整数 $n$。

输出格式

一行一个非负整数，表示去重后的 $\left\{S(\lfloor n/i\rfloor)\right\}_{i\in[1,n]}$ 的异或和。

样例 1

输入

6

输出

19

去重后的集合为 $\{1,4,6,16\}$，异或和为 $19$。

样例 2

输入

233333

输出

354637812

样例 3

输入

9876543210

输出

926874502

样例 4

输入

98765454321

输出

371750957

数据范围与提示

对于 $20\%$ 的数据，$n \leq 10^6$。
对于 $40\%$ 的数据，$n \leq 10^9$。
对于 $60\%$ 的数据，$n \leq 10^{10}$。
对于 $80\%$ 的数据，$n \leq 10^{11}$。
对于 $100\%$ 的数据，$1 \leq n \leq 10^{12}$。

基于 https://loj.ac/p/6783。