### National Olympiad in Informatics, China, 2012

## Day 1, Problem 1 - Random Number Generator

DongDong recently became obsessed with randomization, and random number generators is the foundation of randomization. DongDong plans to use the linear congruential method to generate a number sequence. This method requires for nonnegative integer parameters `m`, `a`, `c`, `X`_{0}. Then, a random sequence <`X _{n}`> can be generated using the following formula:

`X`_{n + 1} = (`a``X _{n}` +

`c`) mod

`m`

where "mod `m`" means to take the remainder after the left hand expression has divided `m`. It can be observed from this equation that the next number in a sequence will always be based off of the current number.

Sequences generated this way are very random in nature, which is why this method has been used extensively. Even randomization functions in the widely used standard libraries of C++ and Pascal employ this method.

DongDong knows that sequences produced this way are very random, but he is also impatient about wanting to know the value `X _{n}` as soon as possible. Since DongDong needs a random number that's one of 0, 1, …,

`g`− 1, he will have to modulo the number

`X`by

_{n}`g`to get the final result. All you have to do is determine the value of

`X`mod

_{n}`g`for DongDong.

### Input Format

The input consists of 6 space-separated integers `m`, `a`, `c`, `X`_{0}, `n`, and `g`. Here, `a`, `c`, and `X`_{0} are nonnegative while `m`, `n`, `g` are positive.

### Output Format

Output a single integer, the value of `X _{n}` mod

`g`.

### Sample Input

11 8 7 1 5 3

### Sample Output

2

### Explanation

The first few terms of <`X _{n}`> are:

k | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

X_{k} | 1 | 4 | 6 | 0 | 7 | 8 |

Thus the answer is `X`_{5} mod `g` = 8 mod 3 = 2.

### Constraints

Test Case | n | m, a, c, X_{0} | m, a | g |
---|---|---|---|---|

1 | n ≤ 100 | m, a, c, X_{0} ≤ 100 | m is prime | g ≤ 10^{8} |

2 | n ≤ 1000 | m, a, c, X_{0} ≤ 1000 | m is prime | |

3 | n ≤ 10^{4} | m, a, c, X_{0} ≤ 10^{4} | m is prime | |

4 | n ≤ 10^{4} | m, a, c, X_{0} ≤ 10^{4} | m is prime | |

5 | n ≤ 10^{5} | m, a, c, X_{0} ≤ 10^{4} | m and a − 1 are prime | |

6 | n ≤ 10^{5} | m, a, c, X_{0} ≤ 10^{4} | m and a − 1 are prime | |

7 | n ≤ 10^{5} | m, a, c, X_{0} ≤ 10^{4} | m and a − 1 are prime | |

8 | n ≤ 10^{6} | m, a, c, X_{0} ≤ 10^{4} | / | |

9 | n ≤ 10^{6} | m, a, c, X_{0} ≤ 10^{9} | m is prime | |

10 | n ≤ 10^{6} | m, a, c, X_{0} ≤ 10^{9} | / | |

11 | n ≤ 10^{12} | m, a, c, X_{0} ≤ 10^{9} | m is prime | |

12 | n ≤ 10^{12} | m, a, c, X_{0} ≤ 10^{9} | m is prime | |

13 | n ≤ 10^{16} | m, a, c, X_{0} ≤ 10^{9} | m and a − 1 are prime | |

14 | n ≤ 10^{16} | m, a, c, X_{0} ≤ 10^{9} | m and a − 1 are prime | |

15 | n ≤ 10^{16} | m, a, c, X_{0} ≤ 10^{9} | / | |

16 | n ≤ 10^{18} | m, a, c, X_{0} ≤ 10^{9} | / | |

17 | n ≤ 10^{18} | m, a, c, X_{0} ≤ 10^{9} | / | |

18 | n ≤ 10^{18} | m, a, c, X_{0} ≤ 10^{18} | m is prime | |

19 | n ≤ 10^{18} | m, a, c, X_{0} ≤ 10^{18} | m is prime | |

20 | n ≤ 10^{18} | m, a, c, X_{0} ≤ 10^{18} | / |

For all of the test cases: `n`, `m`, `g` ≥ 1, and `a`, `c`, `X`_{0} ≥ 0.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 512M

**Added:** Aug 13, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...