XOR of Modular Inverses

In number theory the modular inverse is a very useful tool that allows us to turn a division operation into a multiplication operation. For a natural number a, if there exists an integer I_a satisfying \[ a\times I_{a} \equiv 1 \pmod{M}, \] we call I_a the inverse of a modulo M.

When M is a prime number, by Fermat's Little Theorem for any positive integer a not divisible by M we have \[ a^{M-1} \equiv 1 \pmod{M} \quad\Longrightarrow\quad I_{a} \equiv a^{M-2} \pmod{M}. \]

Given the prime modulus \[ M = 2\,146\,516\,019, \] compute the modular inverse for every natural number a in the interval [1, 233,333,333] and then output the bitwise XOR of all these inverses.

Note: Although the modular inverse of a can be computed using fast exponentiation via Fermat's Little Theorem, a useful recurrence is also known for computing inverses for all numbers in [1, N]:

[ I(1)=1, \qquad I(a)=M-\Bigl\lfloor\frac{M}{a}\Bigr\rfloor\times I(M \bmod a) \pmod{M} \quad \text{for } a>1. ]

inputFormat

This problem has no input. The parameters are fixed as follows:

• N = 233333333
• M = 2146516019

Your program should directly use these fixed values.

outputFormat

Output a single integer — the XOR (bitwise exclusive OR) of the modular inverses (computed modulo M) of all natural numbers in the interval [1, 233333333].

sample

No Input

1907546995