암호 해독

또 그들이 보안 시스템을 바꿨다. 그럼 은행 시스템을 처음부터 다시 해킹해야 한다! 우리는 암호화된 형태의 비밀번호를 가로챘다. 또한 은행에 잠입한 우리 사람이 새 시스템에서 비밀번호가 어떻게 암호화되는지 알려줬다.

시스템의 비밀번호는 어떤 숫자열이다. 이는 다음과 같이 암호화된다. 각 숫자 대신 그 숫자에 대한 우리가 알고 있는 어떤 이차 삼항식의 값을 쓴다. 즉 숫자 $x$ 대신 $ax^2 + bx + c$를 쓰고, 서로 다른 숫자에 대한 값들은 공백 없이 연속해서 쓴다. 예를 들어 암호화 삼항식이 $x^2 - 6x + 9$이고 암호화할 비밀번호가 132라면 암호화 후에는 401이 되고, 비밀번호 198은 43625로 암호화된다.

그러나 암호화된 비밀번호가 항상 유일하게 해독되는 것은 아니다. 예를 들어 같은 삼항식 $x^2 - 6x + 9$와 암호화된 비밀번호 401을 보자. 이는 네 가지 서로 다른 비밀번호 132, 134, 532, 534의 암호화로 나올 수 있다.

게다가 채널 문제로 인해 암호화된 비밀번호를 일부 오류와 함께 가로챘을 수도 있다. 비밀번호에 순차적으로 적용해야 하는 수정 목록이 있다. 각 수정은 암호화된 비밀번호의 어떤 위치에 있는 숫자를 주어진 숫자로 바꾸라는 것을 알려준다.

당신은 팀에서 가장 뛰어난 해커이므로, 비밀번호를 해독할 수 있는 방법의 수를 세는 것이 당신의 임무이다. 방법의 수는 원래 비밀번호에 대해서, 그리고 각 수정 연산 후마다 출력해야 한다. 답이 상당히 클 수 있으므로 $10^9+7$로 나눈 나머지를 구해야 한다.

첫째 줄에는 세 정수 $a$, $b$, $c$ ($0 \le a \le 10$, $-10 \le b, c \le 10$)가 주어진다. 이는 삼항식의 계수이다. 둘째 줄에는 하나의 문자열 $s$가 주어지며, 이는 암호화된 비밀번호로 길이는 $50\,000$을 넘지 않는다. 셋째 줄에는 하나의 정수 $m$ ($0 \le m \le 50\,000$)이 주어지며, 이는 수정의 개수이다. 다음 $m$개의 줄에는 각각 두 수 $p_i$와 $d_i$ ($1 \le p_i \le$ 문자열 $s$의 길이, $0 \le d_i \le 9$)가 주어지며, 이는 숫자를 바꿀 위치와 새로운 숫자 값이다.

삼항식은 $x$에 0부터 9까지의 값을 대입했을 때 음수를 반환하지 않음이 보장된다.

$m + 1$개의 수를 출력한다. 첫 번째 수는 원래 비밀번호를 해독할 수 있는 경우의 수여야 하며, 그다음 각 수정 후의 비밀번호를 해독할 수 있는 경우의 수를 출력한다. 답의 모든 수는 $10^9+7$로 나눈 나머지로 구해야 한다.