12921번 - 제한된 메모리

N개의 정수로 구성된 배열 X에 대한 정보가 주어집니다. 그리고 몇 개의 쿼리가 주어집니다. 각 쿼리는 하나의 정수 q로 표현됩니다. 해당 쿼리에 대해서 배열 X에서 q번째로 작은 원소를 구해야 합니다. 여기서 q는 0-based index입니다. 즉, q=0이면 가장 작은 원소, q=1이면 두 번째로 가장 작은 원소를 구해야 합니다.

이 문제는 너무 쉬워 보일 수 있습니다. 단순히 정렬 후, 쿼리에 대한 답을 출력하면 되기 때문입니다. 이 방법을 막기 위해서 이 문제는 메모리 제한이 너무 작습니다. 배열 X에 대한 정보 전체를 저장할 수 없습니다. 하지만 쿼리의 수는 적어서 쿼리에 대한 정보 전체는 저장할 수 있습니다.

N, x0, a, b가 주어지고 쿼리의 정보가 담긴 배열이 주어집니다. 배열 X를 생성하는 pseudocode는 다음과 같습니다.

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

Integer overflow에 주의하세요.

모든 쿼리에 대한 답을 모두 더한 값을 출력하는 프로그램을 작성하세요.

첫째 줄에는 4개의 정수 N, x0, a, b가 주어집니다. (1 ≤ N ≤ 2,000,000, 0 ≤ x0, a, b ≤ 1,000,000,006)

둘째 줄에는 쿼리의 개수 Q이 주어집니다. (1 ≤ Q ≤ 1000)

셋째 줄에는 쿼리의 각 원소를 나타내는 Q개의 정수가 주어집니다. (0 ≤ q ≤ N-1)

문제의 답을 나타내는 정수를 출력합니다.