Limited Memory

An array $X$ of $N$ integers is defined, but its elements are not given directly. They are generated by the rule below.

Each query is a single integer $q$ and asks for the $q$-th smallest element of $X$. The index $q$ is 0-based, so $q=0$ asks for the smallest element and $q=1$ for the second smallest. A value that appears several times is counted once per appearance.

This looks easy, because sorting the array and reading off the answers would settle it. The memory limit is too small for that: you cannot hold all of $X$ at once. The number of queries is small, so all of the query data does fit.

You are given $N$, $x_0$, $a$, $b$ and the list of queries. The pseudocode that builds $X$ is:

X[0] = x0
for i = 1 to N-1:
    X[i] = (X[i-1] * a + b) % 1000000007

The intermediate product exceeds 32 bits, so watch out for integer overflow.

Write a program that prints the sum of the answers to all queries.

The first line contains the integers $N$, $x_0$, $a$ and $b$, separated by spaces. ($1 \le N \le 2 \times 10^6$, $0 \le x_0, a, b \le 10^9 + 6$)

The second line contains the number of queries $Q$. ($1 \le Q \le 1000$)

The third line contains $Q$ integers, the queries, separated by spaces. ($0 \le q \le N-1$)

Print the sum of the answers to all queries on one line. The value is smaller than $10^{13}$, so it fits in a 64-bit integer.