- 17

## Statement

## Goal

A linear congruential generator (LCG) is a pseudorandom number generator algorithm defined by the recurrence relation:lcg(seed) = (a * seed + c) % m

LCGs are notably used by Java's Math.random(). It is sometimes useful to be able to check the value given by the random number generator a number of steps in the future or in the past, given the current internal seed of the LCG.

You are given the

`seed`, the parameters

`a`,

`c`and

`m`of an LCG and the number of

`steps`.

If

`steps`is positive you must return the result of the composition of the lcg function

`steps`times.

lcg(lcg(...lcg(seed)))

If

`steps`is negative you must return the result of the composition of the reverse of the lcg function.

lcg^-1(lcg^-1(...lcg^-1(seed)))

Hint: The reverse of an LCG is also an LCG. The composition of two LCGs is also an LCG.

Input

**Line 1:**Three space separated integers

`a`,

`c`and

`m`for the LCG parameters.

**Line 2:**An integer

`seed`

**Line 3:**An integer

`steps`

Output

**Line 1 :**The output of the LCG, starting at

`seed`and repeating

`steps`times.

Constraints

0 ≤

0 ≤

1 ≤

0 ≤

-2^63 <=

`a`< 2^640 ≤

`c`< 2^641 ≤

`m`< 2^64,`m`is a power of 20 ≤

`seed`< 2^64-2^63 <=

`steps`< 2^63Example

Input

5 3 8 0 1

Output

3

A higher resolution is required to access the IDE