## NOI '12 P1 - Random Number Generator

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 512M

Problem type
##### National Olympiad in Informatics, China, 2012

DongDong recently became obsessed with randomization, and random number generators are the foundation of randomization. DongDong plans to use the linear congruential method to generate a number sequence. This method requires nonnegative integer parameters , , , . Then, a random sequence can be generated using the following formula:

where "" means to take the remainder after the left hand expression has divided . It can be observed from this equation that the next number in a sequence will always be based on 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 as soon as possible. Since DongDong needs a random number that's one of , he will have to modulo the number by to get the final result. All you have to do is determine the value of for DongDong.

#### Input Specification

The input consists of space-separated integers , , , , , and . Here, , , and are nonnegative while , , are positive.

#### Output Specification

Output a single integer, the value of .

#### Sample Input

11 8 7 1 5 3

#### Sample Output

2

#### Explanation

The first few terms of are:

#### Constraints

Test Case
is prime
is prime
is prime
is prime
and are prime
and are prime
and are prime
/
is prime
/
is prime
is prime
and are prime
and are prime
/
/
/
is prime
is prime
/

For all of the test cases: and .

Problem translated to English by Alex.