Description

$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)$ 的异或和。

Input Format

一行一个正整数 $n$。

Output Format

一行一个非负整数。

5

78

142857

67850062

10000000

505679580

Hint

本题采用捆绑测试

对 $100\%$ 的数据，$1\le n \le 5\times10^{7}$。