Problem Background

__stdcall is playing slay with Edge, but her mouse often malfunctions, causing her great distress. Therefore, she has decided to make you experience the pain caused by Edge as well.

Problem Description

__stdcall has given you n points, with the i-th point having a weight x[i]. For two points u and v, if the result of x[u] xor x[v] has an odd number of 1s in its binary representation, then an Edge is connected between u and v. Now, __stdcall wants you to calculate the total number of Edges.

If you fail to complete the task, __stdcall will make you suffer, and you will lose points for this test case.

Input Format

A line with six integers: n, a, b, c, d, x[0].

n is the number of points, and the weights of each point need to be generated using the following method.

You need to use a, b, c, d, and x[0] to generate an array x, with the generation method as follows:

$x_i = (ax_{i-1}^2 + bx_{i-1} + c) \mod d$

x[i] is the weight of the i-th point, with point numbers ranging from 1 to n.

Output Format

Output a single integer, representing the total number of Edges.

Sample Input and Output

Sample Input #1

8 98 24 20 100 44

Sample Output #1

12

Sample Input #2

1000 952537 601907 686180 1000000 673601

Sample Output #2

249711

Notes

We denote v as the maximum value among the weights.

For the first 20% of the data, n <= 10.

For the first 40% of the data, n <= 100.

For the first 60% of the data, n <= 1000.

For the first 80% of the data, n <= 1e6.

For the first 90% of the data, v <= 1e6.

For 100% of the data, n <= 1e7, v <= 1e9.

It is guaranteed that a, b, c, d, and x[0] are non-negative integers within the int range.

见题面 Input 部分

见题面 Output 部分