XOR of Recursively Defined Function Values

We define a function \(f\) on the positive integers as follows:

\(f(1)=1\) and for any integer \(n>1\), \[ f(n)=\sum_{\substack{d\mid n\\d<n}} f(d)\,\varphi\Bigl(\frac{n}{d}\Bigr), \] where \(\varphi\) denotes Euler's totient function.

Given a positive integer \(n\), compute \[ \bigoplus_{k=1}^{n}\Bigl( f(k) \bmod 2^{32} \Bigr), \] where \(\oplus\) represents the bitwise XOR operation. In other words, compute the XOR of \(f(1)\), \(f(2)\), \(\ldots\), \(f(n)\) after each is reduced modulo \(2^{32}\>.

Note: All formulas are rendered in LaTeX format.

inputFormat

The input consists of a single line containing one positive integer \(n\) (\(1 \le n\le 10^5\) is recommended).

outputFormat

Output a single integer which is the XOR of \(f(k) \bmod 2^{32}\) for all \(1 \le k \le n\>.

sample

1

1