XOR Sum of Divisor Product Function

Given a multiplicative function \(f(x)\) satisfying \(f(p^k)=p^{2k}+k\) for every prime \(p\) and positive integer \(k\), define

\( g(x)=\prod_{d|x} f(d) \bmod (10^9+7) \),

where the product is taken over all positive divisors \(d\) of \(x\).

Your task is to compute the XOR sum of \(g(i)\) for all \(1 \le i \le n\), i.e.,

\(\bigoplus_{i=1}^{n} g(i)\).

Note: By convention, assume \(f(1)=1\) so that \(g(1)=1\).

inputFormat

The input consists of a single integer \(n\) which indicates the range \(1 \le i \le n\) for which \(g(i)\) is computed.

outputFormat

Output a single integer: the XOR sum of \(g(i)\) for all \(1 \le i \le n\).

sample

1

1