Problem Description

After sequencing his cows' genomes, Farmer John is now going to perform genome editing. We know that a genome can be represented as a string consisting of A, C, G, and T. The maximum genome length Farmer John considers is $10^5$.

Farmer John starts from a genome and edits it using the following steps:

1. Cut the current genome at every position between two consecutive equal characters.
2. Reverse all the obtained substrings.
3. Concatenate the reversed substrings in the original order.

For example, if FJ starts from the genome AGGCTTT, he will do the following:

1. Cut between the consecutive G's and T's, obtaining AG | GCT | T | T.
2. Reverse each substring, obtaining GA | TCG | T | T.
3. Concatenate these substrings, obtaining GATCGTT.

Unfortunately, after editing the genome, Farmer John's computer crashed, and he lost the original genome sequence. Also, some positions in the edited genome were corrupted, and these positions are replaced by question marks.

Given the edited genome sequence, help FJ find the number of possible original genome sequences, modulo $10^9+7$.

Input Format

A non-empty string, where each character is one of A, G, C, T, and ?.

Output Format

Output the number of possible original genome sequences modulo $10^9+7$.

?

4

GAT?GTT

3

Hint

Explanation for Sample 2:

Besides the previously mentioned AGGCTTT, there are two other possible original genomes.

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

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

Test Point Properties:

• In test points 1-4, the genome length does not exceed $10$.
• In test points 5-11, the genome length does not exceed $10^2$.
• In test points 12-20, there are no additional constraints.

Problem by: Benjamin Qi.

Translated by ChatGPT 5