Bovine Genetics

Time limit1sMemory limit512 MB

Summary

Count the original genomes that could produce a partly corrupted edited genome (split at equal neighbors, reverse each piece, concatenate), modulo 1e9+7.

Level: Medium6 of 10
Topics: String, Dynamic programming
Solved: No attempts yet

Problem

Farmer John has sequenced the genomes of his cows and now moves on to genomic editing. A genome is a string made of A, C, G, and T. The longest genome Farmer John considers has length $10^5$ .

Farmer John starts with a single genome and edits it with these steps:

Split the genome between every two consecutive equal characters.
Reverse each resulting substring.
Concatenate the reversed substrings in their original order.

For example, if Farmer John starts with AGGCTTT, he performs these steps:

Split between the consecutive Gs and Ts to get AG | GCT | T | T.
Reverse each substring to get GA | TCG | T | T.
Concatenate the substrings to get GATCGTT.

After editing, Farmer John's computer crashed, and he lost the genome he started with. Some parts of the edited genome were damaged and replaced by question marks. Given the edited genome, count the possible original genomes, modulo $10^9+7$ .

Input

A single non-empty string where each character is A, G, C, T, or ?.

Output

Print the number of possible original genomes modulo $10^9+7$ .

Examples2

Example 1
Input
```
?
```
Expected output
```
4
```
Example 2
Input
```
GAT?GTT
```
Expected output
```
3
```