Аналитик Игорь недавно узнал о интересной функции в его текстовом редакторе, которая называется «Заменить все». Игорь заскучал на работе и придумал следующую задачу:
Для двух заданных строк x и y, состоящих только из латинских букв «A» и «B», пара строк (s, t) называется хорошей, если:
- s и t состоят из только из символов «0» и «1».
- 1 ≤ |s|, |t| ≤ n, где запись |z| обозначает длину строки z, а n — фиксированное натуральное число.
- Если заменить все буквы «A» в строках x и y на строку s, а все буквы «B» в строках x и y — на строку 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'), что c' и d' могут быть получены из c и d соответсвенно заменой знаков вопроса на буквы «A» и «B». Ответ нужно вывести по модулю 109 + 7.
Выходные данные
Выведите одно число: ответ на задачу по модулю 109 + 7.
Примечание
В первом примере возможно получить четыре различные пары (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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
A?
?
3
|
2
|
|
2
|
A
B
10
|
2046
|