The series of Functions

You're a given a polynomial P(x) which is defined for all positive integer values of x. Define a series of functions as follows:

F(0,x) = P(x)

Now given a set of values of k and n, compute F(k,n) for each of those values. Since the answer can be very big, please output F(k,n) % 1000000007 (1e9 + 7).

Input

First line of input contains d, the degree of polynomial P. Next line contains d + 1 integers; i-th integer identifying the coefficients of x_i in polynomial P for 0 ≤ i ≤ d. Next line contains Q, the number of queries. Next Q lines contain two integers k and n for each test case.

It is known that 0 ≤ d ≤ 10, 0 ≤ k ≤ 8, 1 ≤ n ≤ 10^9. Output

The output contains Q lines, each line containing value of F(k,n) % 1000000007 for the corresponding query.

Examples