쉽게 제한된 메모리

정수 N개로 이루어진 배열 X가 있다. 쿼리가 몇 개 주어지고, 각 쿼리는 정수 q 하나로 표현된다. 각 쿼리마다 배열 X에서 q번째로 작은 원소를 구해야 한다. q는 0부터 시작하는 인덱스다. 즉 q = 0이면 가장 작은 원소, q = 1이면 두 번째로 작은 원소다.

정렬한 뒤 답을 출력하면 끝나는 쉬운 문제로 보인다. 그래서 이 문제는 메모리 제한을 아주 작게 잡아 그 방법을 막는다. 배열 X 전체를 저장할 수 없다. 대신 쿼리 개수는 적어서 쿼리 정보는 모두 저장할 수 있다.

배열 X는 직접 주어지지 않고, N, x0, a, b로부터 다음 의사코드처럼 생성된다.

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

곱셈에서 오버플로가 일어나지 않도록 주의한다.

모든 쿼리의 답을 더한 값을 출력하는 프로그램을 작성하라.

첫째 줄에 정수 N, x0, a, b가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ x0, a, b ≤ 1,000,000,006)

둘째 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 100)

셋째 줄에 쿼리를 나타내는 정수 Q개가 공백으로 구분되어 주어진다. (0 ≤ q ≤ N-1)

모든 쿼리의 답을 더한 정수 하나를 출력한다.