Набор функций

Рассмотрим многочлен P(x), значение которого определено на всех натуральных значениях x. Определим серию функций следующим образом:

F(0,x) = P(x)

По заданным значениям k и n следует вычислить F(k,n). Поскольку ответ может быть достаточно большим, вывести следует значение F(k,n) % 1000000007 (1e9 + 7).

Входные данные

Первая строка содержит степень d многочлена P. Далее следуют d + 1 целых чисел; i-ое число является коэффициентом при x_i в многочлене P для 0 ≤ i ≤ d. Следующая строка содержит количество запросов Q. Каждая из следующих Q строк содержит два целых значения k и n.

Известно, что 0 ≤ d ≤ 10, 0 ≤ k ≤ 8, 1 ≤ n ≤ 10^9. Выходные данные

Состоит из Q строк, каждая из которых содержит значение F(k,n) % 1000000007 для соответствующего запроса.

Примеры