Problem H
RNG Test

In the olden days dice were used to generate test data

As per usual an absolute truckload of random test data has to be generated for Forritunarkeppni Framhaldsskólanna to test solutions again. Since it’s not feasible to write all the data by hand KFFÍ uses random number generators. The head honchos at KFFÍ are paranoid about the quality of random number generator implementations, so they want to make their own. Atli was thus tasked with making a linear congruential generator. But because Atli overslept, as per usual, someone has to take care of this, that is to say you (as per usual).

A linear congruential generator is defined using three integers $a$, $b$ and $x_0$. We let $f(x)=(ax+b)\mathrm{\%}m$. The percent sign denotes modulus and means the result is calculated modulo $m$. That is to say we take the remainder of the result when it is divided by $m$.

To get the $n$-th random number $f$ is applied $n$ times to the starting value $x_0$. This means the zeroth number is $x_0$, the first number is $f(x_0)$, the next is $f(f(x_0))$ and so on.

Input

The input consists of one line with five integers $a$, $b$, $x_0$, $n$ and $m$ as described above. The integers are non-negative and $m$ is positive.

Output

Print the $n$-th random number the linear congruential generator outputs.

Scoring

10 3 42 42 1009

311

17 18 20 1000000000000000000 100003

41617

1 1 164 500000000000000000 1000000007

500000192