## Random Time Travel

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

Tags

Random, LCG, Seedfinding

Difficulty

Medium

Test cases

Simple forward Test

Input

5 3 8
0
1

Output

3

Validator 1 Validator

Input

5 3 8
3
1

Output

2

Simple backward Test

Input

5 3 8
3
-1

Output

0

Validator 2 Validator

Input

5 3 8
2
-1

Output

3

Java Random 10 steps Test

Input

25214903917 11 281474976710656
123456789
10

Output

265139739725951

NRC forward Validator

Input

1664525 1013904223 4294967296
56416741561
101456

Output

1133829513

Java Random -10 steps Test

Input

25214903917 11 281474976710656
123456789
-10

Output

41935260626811

NRC backward Validator

Input

1664525 1013904223 4294967296
95465457461
-4561

Output

3074731294

Back to the future Test

Input

25214903917 11 281474976710656
123456789
9007199254740990

Output

35623234005539

A long time ago Validator

Input

25214903917 11 281474976710656
123456789
-9007199254740991

Output

119305093197820

Solution language

Solution

Stub generator input