3526. [USACO20Dec Gold]Bovine Genetics

【题目描述】

Farmer John 在对他的奶牛进行基因组测序之后，他现在要进行基因组编辑了！我们知道，基因组可以用一个由 A、C、G、T 组成的字符串来表示。Farmer John 考虑的基因组的最大长度为 $10^5$。

Farmer John 从一个基因组开始，通过下列步骤对其进行编辑：

1. 在所有连续相同字符之间的位置将当前基因组切开。
2. 反转所有得到的子串。
3. 按原先的顺序将反转的子串进行联结。

例如，如果 FJ 从基因组 AGGCTTT 开始，他会执行下列步骤：

1. 在连续的 G 和 T 之间切开，得到 AG | GCT | T | T。
2. 反转每一子串，得到 GA | TCG | T | T。
3. 将这些子串联结起来，得到 GATCGTT。

不幸的是，在对基因组进行编辑之后，Farmer John 的计算机崩溃了，他丢失了他开始时的基因组序列。此外，编辑后的基因组的部分位置遭到了破坏，这些位置用问号代替。

给定编辑后的基因组序列，请帮助 FJ 求出可能的开始时的基因组序列的数量，对 $10^9+7$ 取模。

【输入格式】

一个非空字符串，其中每个字符为 A、G、C、T 和 ? 之一

【输出格式】

输出可能的开始时的基因组序列的数量模 $10^9+7$ 的结果。

【样例输入1】

?

【样例输出1】

4

【样例输入2】

GAT?GTT

【样例输出2】

3

【样例说明】

【样例 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

【数据规模与约定】

对于$ 20\% $的测试数据(测试点$ 1\sim4 $)，满足基因组的长度不超过 $10$。

对于$ 55\% $的测试数据(测试点$ 1\sim11 $)，满足基因组的长度不超过 $10^2$。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Gold 组