Генетика великої рогатої худоби
Після секвенування геномів своїх корів фермер Джон вирішив їх редагувати! Як відомо, геном можна представити рядком, що складається з символів 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