Author: 祝丞阳
斐波那契
题意
定义斐波那契数列 $f$，满足
$$ f(i)= \begin{cases} 1 & i = 0,1\\ f(i - 1) + f(i - 2) & i \geq 2 \end{cases} $$
定义积性函数 $g$，满足
$$ \begin{aligned} g(1) &= 1\\ g(p^k)&=f(k) \end{aligned} $$
求函数 $h = f \times g$，其中 $\times$ 被定义为两个数论函数的狄利克雷卷积。
为了减小输出量，你只需要输出 $h$ 的前 $n$ 项的异或和。
为了实现方便，你只需要输出答案对 $2^{32}$ 取模之后的结果。
输入格式
一行，一个正整数 $n$。
输出格式
一行，一个非负整数表示答案。
样例 1 输入
114
样例 1 输出
1464473808
数据范围与约定
| 子任务编号 | $n \leq$ | 分值 |
|---|---|---|
| $1$ | $2 \times 10^3$ | 3 |
| $2$ | $2 \times 10^6$ | 27 |
| $3$ | $2 \times 10^7$ | 70 |
1s，512M。