E. Супер-Короткий-Полином-Сан
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Эта задача может быть известна в некоторых странах, но как другие страны узнают о таких задачах, если никто их не даёт в контестах?
— XXI Открытый Кубок, Гран-при Токио

Вам даны три целых числа $$$a,b,c$$$.

Пусть $$$F(n)$$$ — многочлен степени $$$2n$$$, определяемый следующим образом.

$$$$$$F(n)=\left ({a x^2+b x+c}\right) ^n$$$$$$

Вам необходимо ответить на $$$q$$$ запросов следующего вида.

  • $$$n\;k$$$: Найдите значение суммы $$$\displaystyle \sum_{i=0}^{k}{\left [ {x^i} \right] F(n)}$$$ по модулю $$$10^9+7$$$$$$^{\text{∗}}$$$.

Однако вам может показаться, что задача слишком простая, если она на этом заканчивается. Так что вот поворот$$$^{\text{†}}$$$: вам нужно отвечать на запросы онлайн.

$$$^{\text{∗}}$$$Здесь, $$$[x^a]F(n)$$$ обозначает коэффициент при $$$x^a$$$ многочлена $$$F(n)$$$.

$$$^{\text{†}}$$$Надеюсь, что задача не стала для вас слишком сложной после поворота. Даже дошколята знают один способ решить задачу — вам просто нужно соптимизировать этот метод в $$$8\,000\,000$$$ раз.

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

Первая строка содержит три целых числа $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a,b,c \le 10^9+6$$$).

Вторая строка содержит количество запросов $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$).

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$n_i'$$$ и $$$k_i'$$$, обозначающих запрос в зашифрованном формате.

Вы должны расшифровать запросы следующим образом.

  • Пусть ответ на $$$i$$$-й запрос по модулю $$$10^9+7$$$ равен $$$ans_i$$$. Здесь $$$ans_0$$$ определяется как $$$0$$$.
  • Тогда значения $$$n$$$ и $$$k$$$ для $$$i$$$-го запроса равны $$$n_i = n_i' \oplus ans_{i-1}$$$ и $$$k_i = k_i' \oplus ans_{i-1}$$$ ($$$0 \le n_i \le 3\cdot 10^5$$$, $$$0 \le k_i \le 2n_i$$$).

Обратите внимание, что как сумма $$$n_i$$$, так и сумма $$$k_i$$$ по всем запросам не ограничены.

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

Для каждого запроса выведите на отдельной строке ответ по модулю $$$10^9+7$$$.

Пример
Входные данные
3 2 1
11
0 0
0 1
0 0
2 1
4 6
3 0
7 7
13 12
25 31
31379 9237
396176013 396306657
Выходные данные
1
1
3
6
1
5
15
27
36
396240845
819003547
Примечание

Расшифрованный пример входных данных выглядит следующим образом. 

3 2 1
11
0 0
1 0
1 1
1 2
2 0
2 1
2 2
2 3
2 4
31415 9265
200000 69420

Здесь многочлен $$$F(n)$$$ соответствует A084608 из OEIS. Не беспокойтесь о ссылке; там нет ничего полезного. Поверьте мне.