Linear Sieve

Problem Description

Given a number $n$, find all primes $p$ in the range $1 \sim n$.

To keep the output from being too large and to prevent precomputing answers from a table, you are also given $a, b$; output the XOR sum of $(a \cdot p + b) \bmod 2^{32}$ over all such primes.

Input Format

The first line contains three integers $n, a, b$.

Output Format

Output one integer: the answer.

Sample Input

100 1 0

Sample Output

64

Constraints

For all data, $1 \leq n \leq 5 \times 10^7$, $0 \leq a, b < 2^{32}$.