P11417 [Sloi 2024]D1T1 精卫


$f(x)$ 为积性函数，且满足 $f(p^k)=p^{2k}+k$（$p$ 为素数）。 令 $g(x)=\prod\limits_{d|x}f(d)\space \bmod\space (10^9+7)$ ，请计算 $g(i)\space (1\le i \le n)$ 的异或和。

一行一个正整数 $n$。

一行一个非负整数。

**本题采用捆绑测试** | Subtask | n | Score | | :----------: | :----------: | :----------: | | $1$ | $\le10^4$ | $10$ | | $2$ | $\le 5\times 10^6$ | $30$ | | $3$ | $\le 2\times 10^7$ | $30$ | | $4$ | $\le 5\times10^7$ | $30$ | 对 $100\%$ 的数据，$1\le n \le 5\times10^{7} $。