Inverses 1

Problem Description

Given a prime $p$, find the inverses of $1\sim n$ modulo $p$.

Since the output could be very large, you only need to output the XOR sum of these inverses.

Input Format

One line with two integers $p, n$.

Output Format

One integer: the XOR sum of the inverses of $1$ to $n$ modulo $p$.

Sample Input

10007 1000

Sample Output

14675

Constraints

For all data, it is guaranteed that $2\leq p\leq 10^9+7$, $1\leq n\leq \min(10^7, p-1)$, and $p$ is prime.

Hint

• You can compute all inverses in linear time using the recurrence $inv[i] = p - \lfloor p/i\rfloor \cdot inv[p \bmod i] \bmod p$ (valid for a prime $p$), or use the fact that $inv[i] \equiv i^{p-2} \pmod p$ with fast exponentiation (slower). XOR the results together at the end.