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

Вхідні дані

Перший рядок містить степінь $d$ многочлена $P$ . Наступний рядок містить $d + 1$ d + 1 цілих чисел: $i$ -те число — це коефіцієнт при $x_{i}$ x_i у $P$ для $0 \leq i \leq d$ 0 \leq i \leq d. Наступний рядок містить кількість запитів $Q$ . Кожен із наступних $Q$ рядків містить два цілих числа $k$ і $n$ .

Гарантується, що $0 \leq d \leq 10$ 0 \leq d \leq 10, $0 \leq k \leq 8$ 0 \leq k \leq 8, $1 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^9.

Вихідні дані

Виведіть $Q$ рядків. Кожен рядок має містити значення $F (k, n) mod 1000000007$ \mathbf{F}(k, n) \bmod 1000000007 для відповідного запиту.

Приклади

Приклад 1

Loading