CF794G.Replace All

Igor the analyst is at work. He learned about a feature in his text editor called "Replace All". Igor is too bored at work and thus he came up with the following problem:

Given two strings x and y which consist of the English letters 'A' and 'B' only, a pair of strings (s, t) is called good if:

• s and t consist of the characters '0' and '1' only.
• 1 ≤ |s|, |t| ≤ n, where |z| denotes the length of string z, and n is a fixed positive integer.
• If we replace all occurrences of 'A' in x and y with the string s, and replace all occurrences of 'B' in x and y with the string t, then the two obtained from x and y strings are equal.

For example, if x = AAB, y = BB and n = 4, then (01, 0101) is one of good pairs of strings, because both obtained after replacing strings are "01010101".

The flexibility of a pair of strings x and y is the number of pairs of good strings (s, t). The pairs are ordered, for example the pairs (0, 1) and (1, 0) are different.

You're given two strings c and d. They consist of characters 'A', 'B' and '?' only. Find the sum of flexibilities of all possible pairs of strings (c', d') such that c' and d' can be obtained from c and d respectively by replacing the question marks with either 'A' or 'B', modulo 109 + 7.

分析员伊戈尔正在工作。他了解到文本编辑器中有一个名为“全部替换”的功能。伊戈尔在工作中感到十分无聊，于是提出了如下问题：

给定两个仅由英文字母 '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 = \text{AAB}$，$y = \text{BB}$，且 $n = 4$，则 $(01,\, 0101)$ 是一组好的字符串对，因为替换后得到的两个字符串均为 "01010101"。

字符串对 $(x,\,y)$ 的灵活性定义为所有好的字符串对 $(s,\,t)$ 的数量。注意：字符串对是有序的，例如 $(0,\,1)$ 和 $(1,\,0)$ 被视为不同的对。

现给出两个仅由字符 'A'、'B' 和 '?' 构成的字符串 $c$ 和 $d$。请计算所有可能的字符串对 $(c',\,d')$ 的灵活性之和，其中 $c'$ 和 $d'$ 分别由 $c$ 和 $d$ 将每个 '?' 替换为 'A' 或 'B' 后得到。结果对 $10^9 + 7$ 取模。

The first line contains the string c (1 ≤ |c| ≤ 3·105).

The second line contains the string d (1 ≤ |d| ≤ 3·105).

The last line contains a single integer n (1 ≤ n ≤ 3·105).

第一行包含字符串 $c$（$1 \leq |c| \leq 3\cdot10^5$）。

第二行包含字符串 $d$（$1 \leq |d| \leq 3\cdot10^5$）。

最后一行包含一个整数 $n$（$1 \leq n \leq 3\cdot10^5$）。

Output a single integer: the answer to the problem, modulo 109 + 7.

输出一个整数：该问题的答案对 $10^9 + 7$ 取模的结果。

For the first sample, there are four possible pairs of (c', d').

If (c', d') = (AA, A), then the flexibility is 0.

If (c', d') = (AB, A), then the flexibility is 0.

If (c', d') = (AA, B), then the flexibility is 2, as the pairs of binary strings (1, 11), (0, 00) are the only good pairs.

If (c', d') = (AB, B), then the flexibility is 0.

Thus, the total flexibility is 2.

For the second sample, there are 21 + 22 + ... + 210 = 2046 possible binary strings of length not greater 10, and the set of pairs of good strings is precisely the set of pairs (s, s), where s is a binary string of length not greater than 10.

对于第一个样例，共有四组可能的 $ (c',,d') $。

若 $ (c',,d') = (\text{AA},,\text{A}) $，则灵活性为 $ 0 $。

若 $ (c',,d') = (\text{AB},,\text{A}) $，则灵活性为 $ 0 $。

若 $ (c',,d') = (\text{AA},,\text{B}) $，则灵活性为 $ 2 $，因为二进制字符串对 $ (1,,11) $、$ (0,,00) $ 是仅有的“好”字符串对。

若 $ (c',,d') = (\text{AB},,\text{B}) $，则灵活性为 $ 0 $。

因此，总灵活性为 $ 2 $。

对于第二个样例，长度不超过 $ 10 $ 的二进制字符串共有 $ 2^1 + 2^2 + \dots + 2^{10} = 2046 $ 个，“好”字符串对的集合恰好是所有形如 $ (s,,s) $ 的字符串对构成的集合，其中 $ s $ 是长度不超过 $ 10 $ 的二进制字符串。