题目描述

先考虑如下问题 A。

给定两个由字符 A、B、? 构成的字符串 $P,Q$。

对于每一种将 $P,Q$ 中所有 ? 分别替换成 A 或 B 的方案，记替换后的两个字符串为 $P',Q'$。

接着枚举所有有序二元组 $(X,Y)$，其中 $X,Y$ 均为非空二进制串，并且满足

$$1\le |X|,|Y|\le n.$$

将 $P',Q'$ 中的字符 A 全部替换成二进制串 $X$，将字符 B 全部替换成二进制串 $Y$。如果替换完成后，两个字符串完全相同，则计入一种合法方案。

问题 A 要求求出所有合法方案数之和，并对 $10^9+7$ 取模。

形式化地，设 $\operatorname{rep}(R,X,Y)$ 表示将字符串 $R$ 中的每个 A 替换为 $X$，每个 B 替换为 $Y$ 后得到的二进制串。则问题 A 的答案为

$$\sum_{P',Q'}\ \sum_{\substack{X,Y\in{0,1}^+\1\le |X|,|Y|\le n}} \left[ \operatorname{rep}(P',X,Y)=\operatorname{rep}(Q',X,Y) \right],$$

其中外层求和枚举所有由 $P,Q$ 中的 ? 替换得到的字符串 $P',Q'$，方括号 $[\cdot]$ 表示若条件成立则取值为 $1$，否则取值为 $0$。

现在，给你两个由 A、B、? 构成的字符串 $S,T$，并有 $q$ 次修改操作。每次修改后，你需要求出当前 $S,T$ 对应的问题 A 的答案。

每次修改形如：

opt x c

• 若 $opt=0$，则将 $S_x$ 修改为字符 $c$；
• 若 $opt=1$，则将 $T_x$ 修改为字符 $c$。

其中 $c\in{\texttt{A},\texttt{B},\texttt{?}}$。

字符串下标从 $1$ 开始。

输入格式

第一行包含三个正整数 $|S|,|T|,n$。

第二行包含一个字符串 $S$。

第三行包含一个字符串 $T$。

第四行包含一个正整数 $q$。

接下来 $q$ 行，每行包含两个非负整数和一个字符：

opt x c

表示一次修改操作。

输出格式

输出 $q$ 行，每行一个整数，表示每次修改后的答案。

答案需要对 $10^9+7$ 取模。

样例 1

输入

1 2 3
?
?B
1
0 1 ?

输出

2

样例 2

输入

1 1 8
A
?
1
0 1 B

输出

260610

样例 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

输出

6
6
20
26
32
94
38
50
50
50

样例 4

输入

3 3 5
A??
?AB
4
0 1 B
0 2 B
0 3 A
1 1 A

输出

4366
292
168
62

样例 5

输入

3 5 13
ABA
BABBA
3
1 5 B
0 2 A
1 2 B

输出

30
126
6

数据范围

对于 $100$ 的数据：

• $|S|,|T|,n\le 10^6$；
• $q\le 6\times 10^3$；
• $\bigl||S|-|T|\bigr|\le 10$；
• $opt\in{0,1}$；
• 当 $opt=0$ 时，$1\le x\le |S|$；
• 当 $opt=1$ 时，$1\le x\le |T|$；
• $c\in{\texttt{A},\texttt{B},\texttt{?}}$。

子任务

子任务编号	分值	$S,T$ 长度上限	$n$ 上限	$q$ 上限	特殊性质
1	6	$4$		$1$	无
2	3	$10^6$			BCD
3					BCE
4					CD
5					CE
6					ABD
7					ABE
8	9	$10^2$			无
9	8	$5\times 10^3$
10	7	$10^6$	$10^6$		D
11					E
12	3				无
13	7			$100$
14	9			$6\times 10^3$	F
15	11		$10^5$	$10^3$	无
16	6		$10^6$	$6\times 10^3$	D
17					E
18	3				无

特殊性质说明：

• 特殊性质 A：修改后，$S,T$ 中不含 A；
• 特殊性质 B：修改后，$S,T$ 中不含 B；
• 特殊性质 C：修改后，$S,T$ 中不含 ?；
• 特殊性质 D：$|S|=|T|$；
• 特殊性质 E：$|S|\ne |T|$；
• 特殊性质 F：若 $opt=0$，则修改前 $S_x$ 不为 ?；若 $opt=1$，则修改前 $T_x$ 不为 ?；并且 $c$ 不为 ?。

对于特殊性质 A、B、C，保证 $q=1,opt=0,x=1,c=S_1$。