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).
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.