Modular Inverses 2

Problem Description

Given a prime $p$, compute the modular inverses of $a_1, a_2, \dots, a_n$ modulo $p$. Since the output could be large, you only need to output the XOR sum of these inverses.

Output one integer: the XOR sum of the inverses of $a_1, a_2, \dots, a_n$. If $a_i = 0$, we take its inverse to be $0$.

To avoid an excessively large input, the sequence $a$ is generated by the following code:

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main() {
    scanf("%d%d%u%u%u", &p, &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        a[i] = rng61()%p;
}

Input Format

One line containing five integers $p, n, A, B, C$.

Output Format

One integer: the XOR sum of the inverses of $a_1, a_2, \dots, a_n$ modulo $p$.

Sample Input

10007 1000 1 2 3

Sample Output

3611

Constraints

For all test cases, $2 \le p \le 10^9 + 7$, $1 \le n \le \min(10^7, p - 1)$, and $0 \le A, B, C < 2^{32}$.