题目描述
问题 A：给两个由 $\text{A,B,?}$ 构成的串，对于将每个 $\text{?}$ 替换为 $\text{A}$ 或 $\text{B}$ 的任意方案，对所有长度 $\in [1,n]$ 的 $01$ 串形成的二元组 $(S,T)$ 求，把 $\text{A}$ 换成 $S$，$\text{B}$ 换成 $T$ 后两串相等的方案数之和，对 $10^9+7$ 取模。
现在，给你两个由 $\text{A,B,?}$ 构成的串 $S,T$，有 $q$ 次询问，每次给定 $opt,x,c$。$opt=0$ 时将 $S_x$ 修改为 $c$，$opt=1$ 时将 $T_x$ 修改为 $c$。对于每次修改后的 $S,T$，求出问题 A 的答案。
输入格式
第一行三个正整数 $|S|,|T|,n$。
第二行一个字符串 $S$。
第三行一个字符串 $T$。
第四行一个正整数 $q$。
接下来 $q$ 行每行两个非负整数与一个 $\text{A,B,?}$ 中的字符 $opt,x,c$。
输出格式
$q$ 行，每行一个正整数，表示答案。
样例一
input
1 2 3 ? ?B 1 0 1 ?
output
2
样例二
input
1 1 8 A ? 1 0 1 B
output
260610
样例三
input
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
6 6 20 26 32 94 38 50 50 50
样例四
input
3 3 5 A?? ?AB 4 0 1 B 0 2 B 0 3 A 1 1 A
output
4366 292 168 62
样例五
input
3 5 13 ABA BABBA 3 1 5 B 0 2 A 1 2 B
output
30 126 6
限制与约定
对于 $100\%$ 的数据：$|S|,|T|,n\leq10^6$，$q\leq6\times10^3$，$\lvert |S|-|T|\rvert\leq10$，$opt\in\{0,1\}$，$opt=0$ 时 $1\leq x\leq |S|$，$opt=1$ 时 $1\leq x\leq |T|$，$c\in\{\text{A},\text{B},\text{?}\}$。
| 子任务编号 | 分值 | $\lvert S\rvert,\lvert T\rvert\leq$ | $n\leq$ | $q\leq$ | 特殊性质 |
|---|---|---|---|---|---|
| $1$ | $6$ | $4$ | $4$ | $1$ | 无 |
| $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$ | 无 |
| $9$ | $8$ | $5\times10^3$ | $5\times10^3$ | $1$ | 无 |
| $10$ | $7$ | $10^6$ | $10^6$ | $1$ | D |
| $11$ | $7$ | $10^6$ | $10^6$ | $1$ | E |
| $12$ | $3$ | $10^6$ | $10^6$ | $1$ | 无 |
| $13$ | $7$ | $10^6$ | $10^6$ | $100$ | 无 |
| $14$ | $9$ | $10^6$ | $10^6$ | $6\times10^3$ | F |
| $15$ | $11$ | $10^6$ | $10^5$ | $10^3$ | 无 |
| $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$ | 无 |
- 特殊性质 A：修改后，$S,T$ 中不含 $\text A$；
- 特殊性质 B：修改后，$S,T$ 中不含 $\text B$；
- 特殊性质 C：修改后，$S,T$ 中不含 $\text ?$；
- 特殊性质 D：$|S|=|T|$；
- 特殊性质 E：$|S|\neq|T|$；
- 特殊性质 F：$opt=0$ 时 $S_x$ 不为 $\text ?$，$opt=1$ 时 $T_x$ 不为 $\text ?$，$c$ 不为 $\text ?$。
对于特殊性质 ABC，保证 $q=1$，$opt=0$，$x=1$，$c=S_1$。