22074번 - Расшифровка 다국어

Так. Опять они изменили систему защиты. Значит, придется взламывать банковскую систему заново, с нуля! Нам удалось перехватить пароль в зашифрованном виде. Также у нас есть свой человек в банке, который рассказал, как шифруются пароли в новой системе.

Мы знаем, что пароль к системе является некоторой последовательностью цифр. Она шифруется следующим образом: вместо каждой цифры записывается значение некоторого известного нам квадратного трехчлена от нее. Таким образом вместо цифры x записывается число ax² + bx + c, числа для разных цифр записываются подряд без пробелов. Например, если шифрующий трехчлен равен x² − 6x + 9, и пароль, который был зашифрован, был равен 132, то после шифрования получится 401, а, например, пароль 198 зашифруется в 43625.

Однако зашифрованный пароль расшифровывается не всегда однозначно. Например, рассмотрим тот же трехчлен x² − 6x + 9 и зашифрованный пароль 401. Он мог получиться шифрованием четырех различных паролей: 132, 134, 532, 534.

Кроме того, мы могли перехватить зашифрованный пароль с некоторыми ошибками из-за проблем в канале. Есть список исправлений, которые требуется последовательно применить к паролю. Каждое исправление сообщает, что надо заменить цифру на некоторой позиции зашифрованного пароля на некоторую заданную цифру.

Так как вы являетесь самым главным хакером в команде, то ваша задача состоит в том, чтобы посчитать каким числом способов можно расшифровать пароль. Число способов необходимо вывести для исходного пароля, а также после каждой операции исправления. Ответы могут быть довольно большими, поэтому требуется найти их по модулю 10⁹+7.

Первая строка содержит три целых числа a, b и c (0 ≤ a ≤ 10, −10 ≤ b, c ≤ 10) — коэффиценты трехчлена. Вторая строка содержит одну строку s — зашифрованный пароль, длина которого не превосходит 50 000. Третья строка содержит единственное целое число m (0 ≤ m ≤ 50 000) —  количество исправлений. Следующие m строк содержат по два числа p_i и d_i (1 ≤ p_i ≤  длины строки s, 0 ≤ d_i ≤ 9) — позиция, в которой требуется заменить цифру и новое значение цифры.

Гарантируется, что трехчлен не принимает отрицательных значений при подстановке вместо x значений от 0 до 9.

Выведите m + 1 число: первое число должно быть равно количеству вариантов расшифровать оригинальный пароль, далее следует вывести количество вариантов расшифровать пароль после каждого исправления. Все числа в ответе должны быть взяты по модулю 10⁹+7.