Problem A: Given two strings consisting of $\text{A, B, ?}$, for every way to replace each $\text{?}$ with $\text{A}$ or $\text{B}$, consider all pairs of $01$-strings $(S, T)$ with lengths in $[1, n]$. Calculate the sum of the number of ways such that the two strings are equal after replacing $\text{A}$ with $S$ and $\text{B}$ with $T$, modulo $10^9+7$.
Now, you are given two strings $S$ and $T$ consisting of $\text{A, B, ?}$, and $q$ queries. Each query provides $opt, x, c$. If $opt=0$, change $S_x$ to $c$; if $opt=1$, change $T_x$ to $c$. For each modified $S$ and $T$, calculate the answer to Problem A.
Input
The first line contains three positive integers $|S|, |T|, n$.
The second line contains a string $S$.
The third line contains a string $T$.
The fourth line contains a positive integer $q$.
The next $q$ lines each contain two non-negative integers and a character from $\{\text{A, B, ?}\}$, denoted as $opt, x, c$.
Output
$q$ lines, each containing a positive integer representing the answer.
Examples
Input 1
1 2 3 ? ?B 1 0 1 ?
Output 1
2
Input 2
1 1 8 A ? 1 0 1 B
Output 2
260610
Input 3
4 6 6 AABA BBB?AB 10 1 4 A 1 3 ? 0 3 A 1 1 ? 1 6 ? 1 5 ? 0 2 B 0 3 ? 1 3 ? 0 4 B
Output 3
6 6 20 26 32 94 38 50 50 50
Input 4
3 3 5 A?? ?AB 4 0 1 B 0 2 B 0 3 A 1 1 A
Output 4
4366 292 168 62
Input 5
3 5 13 ABA BABBA 3 1 5 B 0 2 A 1 2 B
Output 5
30 126 6
Constraints
For $100\%$ of the data: $|S|, |T|, n \leq 10^6$, $q \leq 6 \times 10^3$, $\lvert |S|-|T|\rvert \leq 10$, $opt \in \{0, 1\}$, $1 \leq x \leq |S|$ when $opt=0$, $1 \leq x \leq |T|$ when $opt=1$, $c \in \{\text{A, B, ?}\}$.
| Subtask | Score | $\lvert S\rvert, \lvert T\rvert \leq$ | $n \leq$ | $q \leq$ | Special Property |
|---|---|---|---|---|---|
| $1$ | $6$ | $4$ | $4$ | $1$ | None |
| $2$ | $3$ | $10^6$ | $10^6$ | $1$ | BCD |
| $3$ | $3$ | $10^6$ | $10^6$ | $1$ | BCE |
| $4$ | $3$ | $10^6$ | $10^6$ | $1$ | CD |
| $5$ | $3$ | $10^6$ | $10^6$ | $1$ | CE |
| $6$ | $3$ | $10^6$ | $10^6$ | $1$ | ABD |
| $7$ | $3$ | $10^6$ | $10^6$ | $1$ | ABE |
| $8$ | $9$ | $10^2$ | $10^2$ | $1$ | None |
| $9$ | $8$ | $5\times10^3$ | $5\times10^3$ | $1$ | None |
| $10$ | $7$ | $10^6$ | $10^6$ | $1$ | D |
| $11$ | $7$ | $10^6$ | $10^6$ | $1$ | E |
| $12$ | $3$ | $10^6$ | $10^6$ | $1$ | None |
| $13$ | $7$ | $10^6$ | $10^6$ | $100$ | None |
| $14$ | $9$ | $10^6$ | $10^6$ | $6\times10^3$ | F |
| $15$ | $11$ | $10^6$ | $10^5$ | $10^3$ | None |
| $16$ | $6$ | $10^6$ | $10^6$ | $6\times10^3$ | D |
| $17$ | $6$ | $10^6$ | $10^6$ | $6\times10^3$ | E |
| $18$ | $3$ | $10^6$ | $10^6$ | $6\times10^3$ | None |
- Special Property A: After modification, $S, T$ contain no $\text{A}$.
- Special Property B: After modification, $S, T$ contain no $\text{B}$.
- Special Property C: After modification, $S, T$ contain no $\text{?}$.
- Special Property D: $|S|=|T|$.
- Special Property E: $|S|\neq|T|$.
- Special Property F: When $opt=0$, $S_x$ is not $\text{?}$; when $opt=1$, $T_x$ is not $\text{?}$; $c$ is not $\text{?}$.
For special properties ABC, it is guaranteed that $q=1, opt=0, x=1, c=S_1$.