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

#6783. 简单的函数 加强版

标签: 传统 | 时间限制: 6000 ms | 内存限制: 1024 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$。
对于$70\%$的数据，$n \leq 10^{10}$。
对于$100\%$的数据，$1 \leq n \leq 10^{11}$。

加强自 https://loj.ac/p/6053。