题目描述

给一个素数 $p$，求 $n$ 个数关于 $p$ 的逆元。

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

由于输入也很大，所以输入由你的程序自行生成，生成规则为：

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

这里的ABC为三个随机数种子，你需要读入该种子，然后自动生成 $n$ 个输入，输入的 $n$ 个数保存在了数组 $a$ 里。

输入格式

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

输出格式

一个整数，表示 $a_1,a_2,…,a_n$ 这些数关于 $p$ 的逆元的异或和。数据保证不产生任何 $a_i=0$。

10007 1000 1 2 3

3611

数据范围

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

注意，这个随机数生成器用到了32位无符号整数的自然溢出，如果使用其他语言请自行考虑修改（设置mask）。