시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 23 | 8 | 2 | 11.765% |
Так. Опять они изменили систему защиты. Значит, придется взламывать банковскую систему заново, с нуля! Нам удалось перехватить пароль в зашифрованном виде. Также у нас есть свой человек в банке, который рассказал, как шифруются пароли в новой системе.
Мы знаем, что пароль к системе является некоторой последовательностью цифр. Она шифруется следующим образом: вместо каждой цифры записывается значение некоторого известного нам квадратного трехчлена от нее. Таким образом вместо цифры x записывается число ax2 + bx + c, числа для разных цифр записываются подряд без пробелов. Например, если шифрующий трехчлен равен x2 − 6x + 9, и пароль, который был зашифрован, был равен 132, то после шифрования получится 401, а, например, пароль 198 зашифруется в 43625.
Однако зашифрованный пароль расшифровывается не всегда однозначно. Например, рассмотрим тот же трехчлен x2 − 6x + 9 и зашифрованный пароль 401. Он мог получиться шифрованием четырех различных паролей: 132, 134, 532, 534.
Кроме того, мы могли перехватить зашифрованный пароль с некоторыми ошибками из-за проблем в канале. Есть список исправлений, которые требуется последовательно применить к паролю. Каждое исправление сообщает, что надо заменить цифру на некоторой позиции зашифрованного пароля на некоторую заданную цифру.
Так как вы являетесь самым главным хакером в команде, то ваша задача состоит в том, чтобы посчитать каким числом способов можно расшифровать пароль. Число способов необходимо вывести для исходного пароля, а также после каждой операции исправления. Ответы могут быть довольно большими, поэтому требуется найти их по модулю 109+7.
Первая строка содержит три целых числа a, b и c (0 ≤ a ≤ 10, −10 ≤ b, c ≤ 10) — коэффиценты трехчлена. Вторая строка содержит одну строку s — зашифрованный пароль, длина которого не превосходит 50 000. Третья строка содержит единственное целое число m (0 ≤ m ≤ 50 000) — количество исправлений. Следующие m строк содержат по два числа pi и di (1 ≤ pi ≤ длины строки s, 0 ≤ di ≤ 9) — позиция, в которой требуется заменить цифру и новое значение цифры.
Гарантируется, что трехчлен не принимает отрицательных значений при подстановке вместо x значений от 0 до 9.
Выведите m + 1 число: первое число должно быть равно количеству вариантов расшифровать оригинальный пароль, далее следует вывести количество вариантов расшифровать пароль после каждого исправления. Все числа в ответе должны быть взяты по модулю 109+7.
1 -6 9 401 9 3 9 2 9 1 9 2 0 1 0 3 0 2 1 3 4 1 1
4 4 8 8 4 2 1 2 4 8