Генетика крупного рогатого скота
После секвенирования геномов своих коров фермер Джон перешел к их редактированию! Как известно, геном может быть представлен строкой, состоящей из A, C, G и T. Максимальная длина генома, рассматриваемого фермером Джоном, составляет 10^5.
Фермер Джон начинает с одного генома и редактирует его, выполняя следующие шаги:
Разделите геном между каждыми двумя последовательными равными символами.
Переверните каждую из полученных подстрок.
Объедините перевернутые подстроки вместе в том же порядке.
Например, если ФД начнет с генома AGGCTTT, то он выполнит следующие шаги:
Разделить геном между последовательными G и T, получив AG | GCT | T | T.
Перевернуть каждую подстроку, получив GA | TCG | T | T.
Объединить подстроки вместе, получив GATCGTT.
К сожалению, после редактирования генома компьютер Фермера Джона сломался, и он потерял последовательность генома, с которой первоначально начал работу. Кроме того, некоторые части отредактированного генома были повреждены - они были заменены вопросительными знаками.
Зная последовательность отредактированного генома, помогите ФД определить количество возможных исходных геномов по модулю 10^9 + 7.
Входные данные
Непустая строка, в которой каждый символ является одним из A, G, C, T или ?.
Выходные данные
Выведите количество возможных исходных геномов по модулю 10^9 + 7.
Пример 1
Знак вопроса может быть любым из A, G, C или T.
Пример 2
Существуют два возможных исходных генома помимо AGGCTTT, описанного выше.
AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT