Рассмотрим многочлен \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 }для соответствующего запроса.