问题描述

萌萌哒Salroey最近得到了一个长度为 $n$ 的正整数数列 $S_i$ ，下标从 1 开始标号，她现在想让你对于一个给定正整数 $k$ ，求出 $t_j$ 表示区间 $[j, j+k-1]$ 中所有元素的乘积 $(1 \leq j \leq n-k+1)$ 。为了方便输出，你只需要把所有 $t_j$ 对 $P$ 取模之后，输出它们的异或和。

输入

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

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

$S_1=A$ ;

$S_i=\left(S_{i-1} \times B+C\right) \bmod D$

输出

输出一行一个整数表示 $t_i \bmod P$ 的异或和。

输入输出样例1

样例输入1

4 2 10
5 1 1 1

样例输出1

4

输入输出样例 2

样例输入2

1000 97 96998351
41 1668 505 2333

样例输出2

1749769

数据范围

对于 $20 \%$ 的数据，$n \leq 1000$

对于 $50 \%$ 的数据，$n \leq 2 \times 10^5$

另有 $20 \%$ 的数据，$n \leq 2 \times 10^6 ; n-k \leq 10$

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

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