#1498. 「hyOI2019」henry_y's function

「hyOI2019」henry_y's function

Description

Thanks

https://loj.ac/user/3003
nting this problem and @_rqy for the solution.

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

  1. g(1)=1g(1)=1
  2. g(pc)=pcg(p^c)=p \oplus cpp is prime,\oplus denotes bitwise exclusive or)。
  3. g(ab)=g(a)g(b)g(ab)=g(a)g(b)aa and bb are coprime numbers)。

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


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

https://loj.ac/user/6189

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)f(2)f(n)f(1) \oplus f(2) \oplus \ldots \oplus f(n)

Input

The first line contains a positive integer nn.

Output

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

Sample 1

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%10\% of data,n100n \leq 100

For 30%30\% of data,n50000n \leq 50000

For 50%50\% of data,n106n \leq 10^6

For 100%100\% of data,n107n \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