동전 교환

강호는 동전 수집가다. 강호가 가진 동전의 가치는 모두 1 이상 $D$ 이하의 자연수다. 같은 가치의 동전을 여러 개 가지고 있을 수도 있다. 강호는 임의의 두 동전을 구분할 수 있으며, 두 동전의 가치가 같아도 구분할 수 있다.

준규는 강호가 어떤 동전을 가지고 있는지 알지 못한다. 준규가 아는 것은 강호의 동전으로 $x$원을 만드는 방법의 수뿐이다.

$f(x)$는 강호가 가진 동전으로 $x$원을 만드는 방법의 수이고, 이 값을 1,000,000,007로 나눈 나머지를 $W_x$라고 한다. 준규는 $0 \le i \le D$인 모든 정수 $i$에 대한 $W_i$를 알고 있다.

동전을 서로 구분하므로, 강호가 1원짜리 동전 두 개만 가지고 있다면 $f(0) = 1$, $f(1) = 2$, $f(2) = 1$이고 2보다 큰 모든 $x$에 대해 $f(x) = 0$이다.

강호는 민호에게 동전 일부를 주려고 하며, 어떻게 줄지 고민하고 있다. 강호가 생각한 시나리오는 $Q$개이고 서로 독립적이며, 1번부터 $Q$번까지 번호가 붙어 있다. $i$번째 시나리오는 두 정수 $V_i$와 $N_i$로 이루어지는데, 가치가 $V_i$인 동전 $N_i$개를 민호에게 준다는 뜻이다.

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

첫째 줄에 $D$가 주어진다. ($1 \le D \le 1999$)

둘째 줄에 $W_0, W_1, \dots, W_D$가 주어진다. ($0 \le W_i \le 1000000006$)

셋째 줄에 시나리오의 개수 $Q$가 주어진다. ($1 \le Q \le 2000$)

넷째 줄부터 $Q$개의 줄에 각 시나리오의 $V_i$와 $N_i$가 주어진다. ($1 \le V_i \le D$, $1 \le N_i \le 1000000$)

주어진 $W_i$와 맞아떨어지는 강호의 동전 구성은 여러 가지일 수 있다. 그런 모든 구성에서 시나리오를 그대로 실행할 수 있고 답이 모두 같은 경우만 입력으로 주어진다.

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