После секвенирования геномов своих коров фермер Джон перешел к их редактированию! Как известно, геном может быть представлен строкой, состоящей из A, C, G и T. Максимальная длина генома, рассматриваемого фермером Джоном, составляет 105.

Фермер Джон начинает с одного генома и редактирует его, выполняя следующие шаги:

• Разделите геном между каждыми двумя последовательными равными символами.
• Переверните каждую из полученных подстрок.
• Объедините перевернутые подстроки вместе в том же порядке.

Например, если ФД начнет с генома AGGCTTT, то он выполнит следующие шаги:

• Разделить геном между последовательными G и T, получив AG | GCT | T | T.
• Перевернуть каждую подстроку, получив GA | TCG | T | T.
• Объединить подстроки вместе, получив GATCGTT.

К сожалению, после редактирования генома компьютер Фермера Джона сломался, и он потерял последовательность генома, с которой первоначально начал работу. Кроме того, некоторые части отредактированного генома были повреждены - они были заменены вопросительными знаками.

Зная последовательность отредактированного генома, помогите ФД определить количество возможных исходных геномов по модулю 109 + 7.

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

Непустая строка, в которой каждый символ является одним из A, G, C, T или ?.

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

Выведите количество возможных исходных геномов по модулю 109 + 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