← 返回题目列表

Codeforces · 794/G

G. 全部替换

中文机器翻译题面 查看原题

分析师 Igor 正在工作。他了解了文本编辑器中的一个名为“全部替换”的功能。 Igor 工作太无聊,因此他提出了以下问题:

给定两个仅由英文字母“A”和“B”组成的字符串 x 和 y,如果满足以下条件,则称一对字符串 (s, t) 为良好:

- s 和 t 仅包含字符“0”和“1”。
- 1 ≤ |s|, |t| ≤ n,其中 |z|表示字符串z的长度,n为固定正整数。
- 如果我们将 x 和 y 中出现的所有“A”替换为字符串 s,并将 x 和 y 中出现的所有“B”替换为字符串 t,则从 x 和 y 字符串获得的两个值相等。

例如,如果x = AAB,y = BB,n = 4,则(01, 0101)是好的字符串对之一,因为替换字符串后得到的都是“01010101”。

一对字符串 x 和 y 的灵活性是良好字符串对 (s, t) 的数量。这些对是有序的,例如对 (0, 1) 和 (1, 0) 是不同的。

给你两个字符串 c 和 d。它们由字符“A”、“B”和“?”组成仅有的。求所有可能的字符串对 (c', d') 的灵活性之和,这样可以通过将问号替换为 'A' 或 'B',模 109 + 7 分别从 c 和 d 获得 c' 和 d'。

输入

第一行包含字符串 c (1 ≤ |c| ≤ 3·105)。

第二行包含字符串 d (1 ≤ |d| ≤ 3·105)。

最后一行包含一个整数 n (1 ≤ n ≤ 3·105)。

输出

输出一个整数:问题的答案,模 109 + 7。

示例

输入 #1

A?
?
3

输出 #1

2

输入 #2

A
B
10

输出 #2

2046

注意

对于第一个样本,有四对可能的 (c', d')。

如果 (c', d') = (AA, A),则灵活性为 0。

如果 (c', d') = (AB, A),则灵活性为 0。

如果 (c', d') = (AA, B),则灵活性为 2,因为二进制字符串对 (1, 11), (0, 00) 是唯一好的对。

如果 (c', d') = (AB, B),则灵活性为 0。

因此,总灵活性为 2。

对于第二个样本,有 21 + 22 + ... + 210 = 2046 个可能的长度不大于 10 的二进制字符串,并且好字符串对的集合恰好是对 (s, s) 的集合,其中 s 是长度不大于 10 的二进制字符串。