As an ACMer, GSS is addicted to AC Automaton, i.e. how to AC automatically. GSS believes

that he will implement it in the future, so he works hard on it. However, it’s almost impossible for

machines to understand the problem descriptions with the stateofart natural language processing

technology.

As we all know, nothing can stop GSS. To achieve this great goal and rescue every ACMer, GSS

spares no effort to solve it. One day, an idea occurs to him. What about the entropy? According to

Ludwig Eduard Boltzmann, the entropy can be understood in terms of molecular disorder’ within

a system. Thus, GSS decides to do some research on the entropy of the input files of some ACM

problems. He believes that he can find the law from the input files, then connect it to the output.

After the day he finishes it, every ACMer will be retired.

To find the law from the input files, GSS has already done lots of experiments on these input

files. The modular arithmetic can reach the best performance, so he defines that the entropy of

connecting two numbers a, b is min(a mod b,b mod a).

Generally, the output will be related to every number in the input file. It’s quite easy for GSS to

solve. Why not connect every number with the minimum total entropy? Perfect solution. Please

tell GSS what is the minimum total entropy of connecting all the numbers of an input file.

The input file consists of six numbers n,x 1 ,a,b,c,m, describing an input files you should calculate

the minimum total entropy of it.

n(2 ≤ n ≤ 10 7 ), is the numbers of number in the input file.

x 1 (0 ≤ x 1 < m), is the first number of the input file.

And the rest numbers of the input file can be generated by the following formula:

x i+1 = (ax 2i+ bx i + c) mod m

a,b,c(0 ≤ a,b,c < m), m(2 ≤ m ≤ 3 × 10 6 ), are the parameters of the formula.

(From the above formula, you will find that ACM problem authors are so lazy that they always

generate the datasets randomly.)

Output a number representing the minimum entropy of the given input file.

The numbers of the input file: 2 3 4

x 1 = 2

x 2 = (0 × 2 2 + 1 × 2 + 1) mod 10 = 3

x 3 = (0 × 3 2 + 1 × 3 + 1) mod 10 = 4

The entropy of connecting two numbers:

(2,3) = 1,(2,4) = 0,(3,4) = 1

So we connect (2,3) and (2,4), the total entropy is 0 + 1 = 1.

2017 Wuhan University Programming Contest