You're a given a polynomial \textbf{P}(\textbf{x}) which is defined for all positive integer values of \textbf{x}. Define a series of functions as follows: \textbf{F}(\textbf{0},\textbf{x}) = \textbf{P}(\textbf{x}) \includegraphics{https://static.e-olymp.com/content/bd/bd10f70dace59ac14f84a431fc2c1656940ff145.jpg} Now given a set of values of \textbf{k} and \textbf{n}, compute \textbf{F}(\textbf{k},\textbf{n}) for each of those values. Since the answer can be very big, please output F(\textbf{k},\textbf{n}) \% \textbf{1000000007} (\textbf{1e9} + \textbf{7}). \InputFile First line of input contains \textbf{d}, the degree of polynomial \textbf{P}. Next line contains \textbf{d} + \textbf{1} integers; \textbf{i}-th integer identifying the coefficients of \textbf{x_i} in polynomial \textbf{P} for \textbf{0} ≤ \textbf{i} ≤ \textbf{d}. Next line contains \textbf{Q}, the number of queries. Next \textbf{Q} lines contain two integers \textbf{k} and \textbf{n} for each test case. It is known that \textbf{0} ≤ \textbf{d} ≤ \textbf{10}, \textbf{0} ≤ \textbf{k} ≤ \textbf{8}, \textbf{1} ≤ \textbf{n} ≤ \textbf{10^9}. \textbf{Output} The output contains \textbf{Q} lines, each line containing value of \textbf{F}(\textbf{k},\textbf{n}) \% \textbf{1000000007 } for the corresponding query.