题目描述
在对奶牛的基因组进行测序后,农民约翰开始进行基因组编辑!我们知道,基因组可以用a组成的字符串来表示,
Cs, Gs和Ts。法默正在考虑的基因组的最大长度
约翰是10的5次方
.
农民约翰从一个基因组开始,通过执行
以下步骤:
将基因组拆分为每两个连续相等的字符。
反转每个结果子字符串。
以相同的顺序将反转的子字符串连接在一起。
例如,如果FJ从基因组AGGCTTT开始,那么他将执行
以下步骤:
将连续的g和T分开得到AG | GCT | T | T。
反转每个子串得到GA | TCG | T | T。
将子字符串连接在一起以获得GATCGTT。
不幸的是,编辑完基因组后,农夫约翰的电脑死机了,他
失去了他最初的基因组序列。此外,一些
部分编辑过的基因组已经被破坏,这意味着它们已经被破坏了
用问号代替。
给定编辑过的基因组序列,帮助FJ确定
原始基因组的可能性,模10^9+7
输入格式
非空字符串,其中每个字符是A、G、C、T或?中的一个。
输出格式
可能的原始基因组数对10^9+7取模
输入输出样例
输入#1
?
输出#1
4
说明/提示
问号可以是A、G、C或T中的任何一个。