Набір функцій

Розглянемо многочлен 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 для відповідного запиту.

Приклади