Bovine Genetics

题目描述

在对奶牛的基因组完成测序之后，农夫 John 开始研究基因编辑！我们知道，一个基因组可以表示为由 A、C、G、T 组成的字符串。农夫 John 考虑的基因组最大长度为 $10^5$。

农夫 John 从一个基因组开始，并通过执行以下步骤对其进行编辑： 在每一对相邻且相等的字符之间将基因组切分。 将得到的每个子串分别反转。 按相同顺序将反转后的子串连接起来。

例如，如果 FJ 最初的基因组是 AGGCTTT，那么他会执行如下步骤： 在相邻的 G 和 T 之间切分，得到 AG | GCT | T | T。 将每个子串反转，得到 GA | TCG | T | T。 将子串连接起来，得到 GATCGTT。

不幸的是，在编辑完基因组后，农夫 John 的电脑崩溃了，他丢失了最初的基因组序列。并且，编辑后的基因组有一些部分受损，意味着它们被替换成了问号。

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

输入格式

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

输出格式

输出原始基因组的可能数量，对 $10^9+7$ 取模。

?

4

GAT?GTT

3

提示

问号可以是 A、G、C 或 T 中的任意一个。 有两种可能的原始基因组，除了上面描述的 AGGCTTT 之外。 AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT

TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT 计分（SCORING）： 在测试点 1-4 中，基因组长度最多为 $10$。 在测试点 5-11 中，基因组长度最多为 $10^2$。 在测试点 12-20 中，没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2020|Gold

来源

USACO|2020|Gold