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:
Thus the answer is .
Constraints
Test Case | ||||
---|---|---|---|---|
/ | ||||
/ | ||||
/ | ||||
/ | ||||
/ | ||||
/ |
For all of the test cases: and
.
Problem translated to English by .
Comments