Description

Thanks

nting this problem and @_rqy for the solution.

One day you found a magical function $g(x)$ which satisfies many properties:

1. $g(1)=1$。
2. $g(p^c)=p \oplus c$（$p$ is prime，$\oplus$ denotes bitwise exclusive or）。
3. $g(ab)=g(a)g(b)$（$a$ and $b$ are coprime numbers）。

You were happy to find this function so you wanted to find $\sum_{i=1}^n g(i)$.

---

However, eventually you couldn't come up with any ideas. Therefore, you asked

henry_y: Isn't this problem from LibreOJ?

henry_y thought this problem was too simple so he asked you another problem.

Let

$$f(n) = \left( \sum_{i = 1}^n \left\lfloor \frac ni \right\rfloor^2 g(i) \right) \bmod 998244353 $$

Find $f(1) \oplus f(2) \oplus \ldots \oplus f(n)$。

Input

The first line contains a positive integer $n$.

Output

The first line contains a non-negative integer, representing the answer.

5

61

10

207

10000

287416092

Limits And Hints

Update 2019/7/10 20:23：We have set the time limit to 1500ms. The using time of standard program on each test did not exceed 500ms, though, so please notice the constant factor's effect.

For $10\%$ of data，$n \leq 100$。

For $30\%$ of data，$n \leq 50000$。

For $50\%$ of data，$n \leq 10^6$。

For $100\%$ of data，$n \leq 10^7$。

Problem information

• Idea:
  https://loj.ac/user/3003
• Solution: @_rqy
• Std / Data:
  https://loj.ac/user/1408
• Testing:
  https://loj.ac/user/10399