시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB85375.000%

문제

강호는 동전 수집가이다. 강호가 가지고 있는 모든 동전의 가치는 1보다 크거나 같고 D보다 작거나 같은 자연수이다. 같은 가치를 갖는 동전을 여러개 가지고 있을 수도 있다. 강호는 임의의 두 동전을 구분할 수 있으며, 두 동전의 가치가 같다고 해도 동전을 구분할 수 있다.

준규는 강호가 어떤 동전을 가지고 있는지 알지 못한다. 준규가 알고 있는 정보는 강호가 가지고 있는 동전을 사용해서 x원을 만드는 방법의 수만 알고 있다.

f(x)를 강호가 가지고 있는 동전을 사용해서 x원을 만드는 방법의 수이고, 이 값을 1,000,000,007로 나눈 나머지를 Wi라고 한다. 준규가 알고 있는 정보는 0 ≤ i ≤ D인 모든 정수 i에 해당하는 Wi이다.

예를 들어, 강호가 가지고 있는 동전이 1원짜리 두 개라면, f(0) = 1, f(1)= 2, f(2) = 1이고, 2보다 큰 모든 x의 f(x) 값은 0이 된다.

강호는 민호에게 동전 일부를 주려고 한고, 어떻게 동전을 줄지 생각하고 있다. 강호는 Q개의 독립적인 시나리오를 생각했으며, 이 시나리오는 1번부터 Q번까지 번호가 매겨져 있다.

i번째 시나리오는 두 가지 정수 Ni과 Vi로 이루어져 있는데, 가치가 Vi인 동전 Ni개를 민호에게 준다는 의미이다.

각각의 시나리오에 대해서, 동전을 민호에게 준 이후에 f(D)를 1,000,000,007로 나눈 나머지의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 D(1 ≤ D ≤ 1999)가 주어진다.

둘째 줄에는 W0, W1, ..., WD가 주어진다. (0 ≤ Wi ≤ 1,000,000,006)

셋째 줄에는 시나리오의 개수 Q(1 ≤ Q ≤ 2,000)가 주어진다. 

넷째 줄부터 Q개의 줄에는 시나리오의 정보 Vi와 Ni가 주어진다. (1 ≤ Vi ≤ D, 1 ≤ Ni ≤ 1,000,000)

Wi로 만들 수 있는 동전이 있으며, 각각의 시나리오 Vi, Ni에 해당하는 값을 만들 수 있는 경우만 입력으로 주어진다.

입력으로 주어진 Wi를 가지고 만들 수 있는 강호의 동전은 여러 가지 방법이 있다. 이 모든 방법에 대해서 각각의 시나리오는 같은 정답을 구할 수 있는 경우면 입력으로 주어진다.

출력

각각의 시나리오에 대해서, f(D)를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

2
1 4 6
3
1 1
1 2
1 3

예제 출력 1

3
1
0

예제 입력 2

8
1 2 1 0 0 0 0 0 7
4
8 1
8 7
1 1
1 2

예제 출력 2

6
0
7
7

예제 입력 3

5
1 2 3 6 9 14
10
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2

예제 출력 3

9
10
11
12
13
6
8
8
10
12

예제 입력 4

1
1 0
2
1 1
1 1000000

예제 출력 4

1000000006
999000007

출처