题目描述

萌萌哒$\red{Salroey}$最近得到了一个长度为$\red{n}$的正整数数列$\red{S_i，}$下标从$\red{1}$开始标号， 她现在想让 你对于一个给定正整数$\red{k，}$求出$\red{t_j}$表示区间$\red{[j,j+k-1]}$中所有元素的乘积$\red{(1≤}$$\red{j≤}$$\red{n-k+1)}$。

为了方便输出，你只需要把所有$\red{t_j}$对$\red{P}$取模之后，输出它们的异或和。

输入格式

第一行三个正整数$\red{n,k,P，}$分别表示序列长度，区间长度和模数。

第二行四个整数$\red{A,B,C, D，}$用来生成数据，$\red{S_i}$定义如下:

$\red{S_1= A}$;$\red{S_i=(S_{i-1}\times B+C)~ mod~ D}$

输出格式

输出一行一个整数表示$\red{t_i ~mod~ P}$的异或和。

样例

输入样例1

4 2 10
5 1 1 10

输出样例1

4

输入样例2

1000 97 96998351
41 1668 505 2333

输出样例2

1749769

提示

对于$\red{20\%}$的数据，$\red{n≤}$$\red{1000}$

对于$\red{50\%}$的数据，$\red{n≤}$$\red{2\times 10^5}$

另有$\red{20\%}$的数据，$\red{n≤}$$\red{2\times 10^6}$;$\red{n-k≤}$$\red{10}$

对于$\red{100\%}$的数据，$\red{1≤}$$\red{k≤}$$\red{n≤}$$\red{2\times 10^7}$;$\red{0≤}$$\red{A,B,C< D≤}$$\red{10^9}$;$\red{1≤}$$\red{P≤}$$\red{10^9}$

在所有数据中均匀分布着$\red{50\%}$的数据满足$\red{P}$是质数，这$\red{50\%}$的数据中有$\red{50\%}$满足$\red{P≤}$$\red{10^7}$。