Password decryption

They changed the security system again. So we have to break into the bank system from scratch! We managed to intercept the password in encrypted form. We also have a person inside the bank who told us how passwords are encrypted in the new system.

The system password is a sequence of digits. It is encrypted as follows: instead of each digit, we write the value of a known quadratic trinomial evaluated at that digit. That is, instead of the digit $x$ we write the number $ax^2 + bx + c$, and the numbers for different digits are written consecutively without spaces. For example, if the encrypting trinomial is $x^2 - 6x + 9$ and the password being encrypted is 132, then after encryption we get 401; for instance, the password 198 is encrypted to 43625.

However, an encrypted password is not always decrypted uniquely. For example, consider the same trinomial $x^2 - 6x + 9$ and the encrypted password 401. It could result from encrypting four different passwords: 132, 134, 532, 534.

Moreover, we might have intercepted the encrypted password with some errors due to channel problems. There is a list of corrections that must be applied to the password in sequence. Each correction says to replace the digit at some position in the encrypted password with a given digit.

Since you are the chief hacker on the team, your task is to count the number of ways to decrypt the password. The number of ways must be output for the original password and after each correction operation. The answers can be quite large, so you need to find them modulo $10^9+7$.

The first line contains three integers $a$, $b$, and $c$ ($0 \le a \le 10$, $-10 \le b, c \le 10$), the coefficients of the trinomial. The second line contains a single string $s$, the encrypted password, whose length does not exceed $50\,000$. The third line contains a single integer $m$ ($0 \le m \le 50\,000$), the number of corrections. The following $m$ lines each contain two numbers $p_i$ and $d_i$ ($1 \le p_i \le$ the length of the string $s$, $0 \le d_i \le 9$), the position at which to replace the digit and the new digit value.

It is guaranteed that the trinomial does not take negative values when substituting values from 0 to 9 for $x$.

Output $m + 1$ numbers: the first number must be the number of ways to decrypt the original password, followed by the number of ways to decrypt the password after each correction. All numbers in the answer must be taken modulo $10^9+7$.