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

问号可以是 A、G、C 和 T 中的任意一个。

输入样例：

GAT?GTT

输出样例：

3

除了在之前说明过的 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 没有额外限制。