181. X-Sequence

time limit per test: 0.25 sec / memory limit per test: 4096 KB

Let { \(x_i\)} be the infinite sequence of integers:

1) \(x_0\) = A;

2) \(x_i\) = (alpha * \(x_{i-1}^2\) + beta * \(x_{i-1}\) + gamma) mod M, for i >= 1.

Your task is to find \(x_k\) if you know A, alpha, beta, gamma, M and k.

Input

Given A (1 <= A <= 10000), alpha (0 <= alpha <= 100), beta (0 <= beta <= 100), gamma (0 <= gamma <= 100), M (1 <= M <= 1000), k (0 <= k <= 10^9). All numbers are integer.

Output

Write \(x_k\).

Example(s)

Sample Input	Sample Output
1 1 1 1 10 1	3