Title Description

Dong Dong has recently become obsessed with random algorithms, and random numbers are the basis for generating random algorithms. Dong Dong is preparing to use Linear Congruent Me thod to generate a random sequence. This method requires setting four non negative integer parameters $m, a, c, X[0]$, and generating a series of random numbers $X[n]\times X[n+1]=(a\times X[n]+c)$ $mod$ $m$, where $mod$ $m$ represents the remainder of the previous number divided by m. From this equation, it can be seen that the next number in this sequence is always generated by the previous number. The sequence generated by this method has the property of a random sequence, so this method is widely used, including the commonly used C++and Pascal library functions for generating random numbers, which also use this method. Dong Dong knows that the sequence generated in this way has good randomness, but he still wants to know as soon as possible what $X[n]$is. Since the random number required by the building is between $0, 1,..., g-1$, he needs to divide $X[n]$ by $g$ and take the remainder to get the number he wants, which is $X [n]$ $mod$ $g$. You just need to tell the building what the number he wants is $X[n]$ $mod$ $g$.

Input format

$6$ integers separated by spaces $m, a, c, X[0], n$, and $g$, where $a, c, X[0]$are non negative integers and $m, n, g$ are positive integers

Output format

Output a number, which is $X[n]$ $mod$ $g$.

Example

11 8 7 1 5 3

2

Example Description

Calculated as $X[n]=X [5]=8$, therefore $(X[n]$ $mod$ $g)=(8$ $mod$ $3)=2$

Data scale and agreement

For all data: $n\ge 1, m\ge 1, a\ge 0, c\ge 0, X[0]\ge 0, g\ge 1$, $g\le10^8$