Фермер Джон занялся редактированием геномов.
Как известно, геном может быть представлен строкой состоящей из символов
'A', 'C', 'G', 'T'. Максимальная длина строки генома, рассматриваемая ФД
есть 10^5.
ФД начинает с одного генома и редактирует его, выполняя следующие шаги:
- Разделяет геном между каждыми двумя последовательными равными символами.
- Реверсирует каждую из полученных подстрок.
- Конкатенирует реверсированные подстроки в том же порядке.
Например, если ФД начинает с генома AGGCTTT, то он выполнит следующие шаги:
- Разделит между последовательными равными символами G и T получит AG | GCT | T | T.
- Реверсирует каждую подстроку, получит GA | TCG | T | T.
- Конкатенирует реверсированные подстроки, получит GATCGTT.
К несчастью, после редактирования генома компьютер ФД сломался, и ФД потерял
последовательность генома, с которого он начинал. Более того, некоторые части
отредактированного генома повредились, заменившись на знак '?'.
По заданной последовательности отредактированного генома помогите ФД определить
количество возможностей для стартового генома по модулю \(10^9+7\).
ФОРМАТ ВВОДА: (с клавиатуры / stdin):
Непустая строка символов , где каждый символ один из A, G, C, T, ?.
ФОРМАТ ВЫВОДА: (на экран / stdout):
Количество возможных оригинальных геномов по модулю \(10^9+7\).
Ваш ответ: