题目描述

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$ 的结果。

?

4

GAT?GTT

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