Фермер Джон зайнявся редагуванням геномів. Як відомо, геном може бути представлений рядком символів 'A', 'C', 'G', 'T'. Максимальна довжина рядка геному, що розглядається ФД є 10^5.

ФД починає з одного геному і редагує його, виконуючи такі кроки:

1. Розділяє геном між кожними двома послідовними рівними символами.
2. Реверсує кожен із отриманих підрядків.
3. Конкатенує реверсовані підрядки в тому ж порядку.

Наприклад, якщо ФД починає з геному AGGCTTT, він виконає такі кроки:

1. Розділить між послідовними рівними символами G та T отримає AG | GCT | T | T.
2. Реверсує кожен підрядок, отримає GA | TCG | T | T.
3. Конкатенує реверсовані підрядки, отримає GATCGTT.

На жаль, після редагування геному комп'ютер ФД зламався, і ФД втратив послідовність геному, з якого він починав. Більше того, деякі частини відредагованого геному пошкодилися, замінившись на знак '?'.

За заданою послідовністю відредагованого геному допоможіть ФД визначити кількість можливостей для стартового геному за модулем \(10^9+7\).

Формат вхідних даних

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

Формат вихідних даних

Кількість можливих оригінальних геномів за модулем \(10^9+7\).

Приклад вхідних даних

?

Приклад вихідних даних

4

Замість ? може бути будь-який з символів A, G, C, T.

Приклад вхідних даних

GAT?GTT

Приклад вихідних даних

3

Крім описаного раніше можуть бути ще два оригінальні геноми, що дають отриманий геном:

AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT

TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT

ОЦІНЮВАННЯ:

• У тестах 1-4 довжина геному не перевищує \(10\).
• У тестах 5-11 довжина геному не перевищує \(10^2\).
• У тестах 12-20 немає додаткових обмежень.