The series of Functions#1176
Sign in

The series of Functions

20 seconds
64 megabytes
Easy

Let be a polynomial defined for all natural values of . Define the following series of functions:

\mathbf{F}(0, x) = \mathbf{P}(x)

Given values and , compute \mathbf{F}(k, n). Since the result can be very large, output \mathbf{F}(k, n) \bmod 1000000007 (10^9 + 7).

Input

The first line contains the degree of the polynomial . The next line contains d + 1 integers: the -th integer is the coefficient of x_i in , for 0 \leq i \leq d. The next line contains the number of queries . Each of the following lines contains two integers and .

It is guaranteed that 0 \leq d \leq 10, 0 \leq k \leq 8, 1 \leq n \leq 10^9.

Output

Output lines. Each line should contain the value \mathbf{F}(k, n) \bmod 1000000007 for the corresponding query.

Examples

Example 1

Loading
Loading