Genome Editing

Farmer John performed genome sequencing of his cows and is now editing the genome. A genome is represented by a string consisting of the characters A, C, G, T. The length of the genome does not exceed \(10^5\).

The editing process is performed on an initial genome \(R\) as follows:

1. Scan the genome \(R=r_0r_1\dots r_{n-1}\) from left to right. Whenever two adjacent characters are equal (i.e. \(r[i]=r[i+1]\)), make a cut between them. (If \(r[i]\) and \(r[i+1]\) are different, do not cut.)
2. For each resulting segment, reverse the segment.
3. Concatenate the reversed segments in their original order to obtain a new string \(S\).

For example, if Farmer John starts with the genome AGGCTTT, then:

• He finds that the characters at positions 1 and 2 are both G and positions 4 and 5 are both T, so he makes cuts yielding segments: AG, GCT, T and T.
• Reversing each segment gives: GA, TCG, T and T.
• Concatenating these produces GATCGTT.

Unfortunately, after editing the genome his computer crashed and he lost the original genome \(R\). Moreover, some positions in the edited genome \(S\) have been damaged and are replaced by a question mark ?.

It can be shown that the transformation defined above is a permutation on the set of all genome strings of length \(n\). In other words, for every string \(S\) of length \(n\) over \(\{A,C,G,T\}\) there is exactly one original genome \(R\) that yields \(S\) after editing.

Your task is: Given the edited genome (with some characters missing, denoted by ?), count the number of possible original genome sequences. Since the answer can be very large, output it modulo \(10^9+7\). Note that each ? can be replaced by any of the four characters A, C, G, T.

Observation: Because the editing transformation is a permutation, for every fully specified edited genome \(S\) there is exactly one original genome \(R\) that produces it. Therefore, the number of possible original genomes is equal to the number of ways to fill in the missing positions. If there are \(q\) question marks, the answer is \(4^q \bmod (10^9+7)\).

inputFormat

The input consists of a single line containing the edited genome string \(S\) of length \(n\) (\(1 \le n \le 10^5\)). The string consists of characters from the set \(\{A, C, G, T, ?\}\), where ? represents a damaged position.

outputFormat

Output a single integer denoting the number of possible original genome sequences \(R\) that, after editing, yield a string consistent with the given edited genome. The result should be given modulo \(10^9+7\).

sample

GATCGTT

1