G. Заменить все
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аналитик Игорь недавно узнал о интересной функции в его текстовом редакторе, которая называется «Заменить все». Игорь заскучал на работе и придумал следующую задачу:

Для двух заданных строк 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.

Входные данные

Первая строка содержит строку c (1 ≤ |c| ≤ 3·105).

Вторая строка содержит строку d (1 ≤ |d| ≤ 3·105).

Последняя строка содержит целое число n (1 ≤ n ≤ 3·105).

Выходные данные

Выведите одно число: ответ на задачу по модулю 109 + 7.

Примеры
Входные данные
A?
?
3
Выходные данные
2
Входные данные
A
B
10
Выходные данные
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.