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 ≤ a < 2^64
0 ≤ c < 2^64
1 ≤ m < 2^64, m is a power of 2
0 ≤ seed < 2^64
-2^63 <= steps < 2^63
Example
Input
```5 3 8
0
1```
Output
`3`

Tags
RandomLCGSeedfinding

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