Розглянемо многочлен \textbf{P}(\textbf{x}), значення якого визначено на всіх натуральних значеннях \textbf{x}. Означимо серію функцій наступним чином: \textbf{F}(\textbf{0},\textbf{x}) = \textbf{P}(\textbf{x}) \includegraphics{https://static.e-olymp.com/content/bd/bd10f70dace59ac14f84a431fc2c1656940ff145.jpg} За заданими значеннями \textbf{k} і \textbf{n} слідт обчислити \textbf{F}(\textbf{k},\textbf{n}). Оскільки відповідь може бути досить великою, вивести потрібно значення F(\textbf{k},\textbf{n}) \% \textbf{1000000007} (\textbf{1e9} + \textbf{7}). \InputFile Перший рядок містить степінь \textbf{d} многочлена \textbf{P}. Далі йде \textbf{d} + \textbf{1} цілих чисел; \textbf{i}-е число є коефіцієнтом при \textbf{x_i} у многочлені \textbf{P} для \textbf{0} ≤ \textbf{i} ≤ \textbf{d}. Наступний рядок містить кількість запитфі \textbf{Q}. Кожен з наступних \textbf{Q} рядків містить два цілих значення \textbf{k} і \textbf{n}. Відомо, що \textbf{0} ≤ \textbf{d} ≤ \textbf{10}, \textbf{0} ≤ \textbf{k} ≤ \textbf{8}, \textbf{1} ≤ \textbf{n} ≤ \textbf{10^9}. \textbf{ Вихідні дані} Вихідні дані складаються з \textbf{Q} рядків, кожен з яких містить значення \textbf{F}(\textbf{k},\textbf{n}) \% \textbf{1000000007 }для відповідного запиту.