[USACO20DEC] Bovine Genetics G
题目描述
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说明
### 样例 2 解释：
除了在之前说明过的 AGGCTTT 之外，还有两种可能的开始时的基因组。
`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 没有额外限制。
供题：Benjamin Qi