Problem J: Range

Problem J: Range

Time Limit: 3 Sec  Memory Limit: 512 MB
Submit: 29  Solved: 4
[Submit][Status][Web Board]

Description

LowbieH has a  positive sequence {\(S_i\)} of length \(n\), numbered from 1 to n. Now she gives you a number k, and asks you to calculate all \(t_j\), which represents the product of all elements in interval \([j,j+k-1](1<=j<=n-k+1)\).

For smaller input, \(S_i\) can be calculated as follow : \(S_1 = A, S_i = (S_{i-1} * B + C) \ mod \ D (2 <= i <= n)\)
For smaller output, you need just output the xor sum of all \(t_j\) module P.


Input

Input contains two lines.

There are three integers \(n,k,P\) in the first line.

There are four integers \(A,B,C,D\) in the second line.

For all test cases, \(1<=k<=n<=2*10^7, 0<=A,B,C<D<=10^9,1<=P<=10^9\).

Output

Only one line, representing the xor sum of all \(t_j\) module P.

Sample Input

4 2 10
5 1 1 10

Sample Output

4

HINT

[Submit][Status]