Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

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。