CF794G Replace All

分析员 Igor 正在工作。他发现了文本编辑器中的一个“全部替换”功能。Igor 对工作感到无聊，于是他想出了如下问题： 给定两个仅由英文字母 'A' 和 'B' 组成的字符串 $x$ 和 $y$，一对字符串 $(s,t)$ 被称为“好对”，当且仅当： - $s$ 和 $t$ 均由字符 '0' 和 '1' 组成。 - $1 \leq |s|, |t| \leq n$，其中 $|z|$ 表示字符串 $z$ 的长度，$n$ 是一个固定的正整数。 - 如果我们把 $x$ 和 $y$ 中所有的 'A' 替换为字符串 $s$，把所有的 'B' 替换为字符串 $t$，则最终由 $x$ 和 $y$ 得到的新字符串必须相等。 例如，若 $x = \mathrm{AAB}$，$y = \mathrm{BB}$ 且 $n=4$，那么 $(01, 0101)$ 是一个“好对”，因为替换后两个字符串均为 "01010101"。 字符串对 $x$ 和 $y$ 的“灵活度”定义为“好对”$(s,t)$ 的数量。注意“好对”是有序的，例如 $(0,1)$ 和 $(1,0)$ 被视为不同的对。 给定两个仅由字符 'A'、'B' 和 '?' 组成的字符串 $c$ 和 $d$，你可以把 $c$ 和 $d$ 中的每一个 '?' 替换为 'A' 或 'B'，从而得到一组新的字符串对 $(c', d')$。请你求所有可能的 $(c', d')$ 的灵活度之和，结果对 $10^9+7$ 取模。

第一行给出字符串 $c$（$1 \leq |c| \leq 3 \cdot 10^5$）。 第二行给出字符串 $d$（$1 \leq |d| \leq 3 \cdot 10^5$）。 最后一行给出一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）。

输出一个整数，表示答案，对 $10^9+7$ 取模。

对于第一个样例，共有四组可能的 $(c', d')$。 - 若 $(c', d') = (\mathrm{AA}, \mathrm{A})$，则灵活度为 $0$。 - 若 $(c', d') = (\mathrm{AB}, \mathrm{A})$，则灵活度为 $0$。 - 若 $(c', d') = (\mathrm{AA}, \mathrm{B})$，则灵活度为 $2$，分别对应 $(1, 11)$ 和 $(0, 00)$ 两组二进制字符串是“好对”。 - 若 $(c', d') = (\mathrm{AB}, \mathrm{B})$，则灵活度为 $0$。 因此，总灵活度为 $2$。 对于第二个样例，所有长度不超过 $10$ 的二进制串共有 $2^1 + 2^2 + \cdots + 2^{10} = 2046$ 个，而所有 $(s, s)$ 这样的二进制串对均为“好对”。 由 ChatGPT 5 翻译