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