逆元2

题目描述

给一个素数 $p$，求$a_1, a_2, \dots, a_n$关于$p$的逆元。

由于输出可能很大，只需要求这些逆元的异或和即可。

输入格式

一行，五个整数$p, n, A, B, C$。

为了防止输入过大，$a$用下面代码生成。

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;
}

输出格式

一个整数，表示$a_1, a_2, \dots, a_n$这些数关于$p$的逆元的异或和。如果$a_i = 0$，我们认为逆元为$0$。

样例输入

10007 1000 1 2 3

样例输出

3611

数据范围

对于所有数据，保证$2\leq p\leq 10^9+7, 1\leq n\leq \min(10^7, p-1), 0\leq A, B, C < 2^{32}$。