题目描述

这是一个很简单的问题。

给你一个整数 $x$，小 i 有 $n$ 个问题问你，每次询问给出一个整数 $t$，你需要求出 $x^t$ 对 $p$ 取模的值。

由于输入很大，你需要使用一下函数来读取每次输入的 t。 由于输出也很大，最终你只需要输出所有答案的异或和。

unsigned int seed, mod; 
int read() { 
	seed ^= seed >> 13; 
	seed ^= seed << 17; 
	seed ^= seed >> 19; 
	return seed % mod; 
} 

seed 与 mod 的值在最开始给定。

输入格式

第一行五个整数分别为 $n, x, p, seed, mod$。

$1 \\leq n \\leq 10^7$。

$0 \\leq x \\leq mod$。

$1 \\leq p, seed, mod \\leq 10^9 + 7$。

注意，$p$ 不一定是个质数。

输出格式

一行一个整数代表所有询问的答案的异或，即：

$ans_1\\ xor\\ ans_2\\ xor\\ \\dots\\ xor\\ ans_n$。

样例

20 2 1000000007 50 20

166240

10000000 39 1000000007 50 1000000003

1026313066

提示

快速幂过不了哦~~~~