← 返回题目列表

Codeforces · 520/C

C. DNA 比对

中文机器翻译题面 查看原题

Vasya 对生物信息学产生了兴趣。他要写一篇关于相似环状DNA序列的文章,因此他发明了一种确定环状序列相似性的新方法。

假设字符串s和t的长度n相同,则函数h(s, t)定义为s和t各自的符号相同的位置数。函数 h(s, t) 可以用来定义 Vasya 距离 ρ(s, t) 的函数:

$$\rho(s,t) = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} h(\text{shift}(s,i), \text{shift}(t,j))。$$

ρ("AGC", "CGT") =

h("AGC", "CGT") + h("AGC", "GTC") + h("AGC", "TCG") +

h("GCA", "CGT") + h("GCA", "GTC") + h("GCA", "TCG") +

h("CAG", "CGT") + h("CAG", "GTC") + h("CAG", "TCG") =

1 + 1 + 0 + 0 + 1 + 1 + 1 + 0 + 1 = 6

Vasya 在互联网上发现了一个长度为 n 的字符串 s。现在他想计算有多少根弦 t 使得与弦 s 的 Vasya 距离达到最大可能值。从形式上来说,t 必须满足方程:$$\rho(s,t) = \max_{u:|u|=|s|} \rho(s,u)$$。

Vasya 无法尝试所有可能的字符串来找到答案,因此他需要您的帮助。由于答案可能非常大,因此计算此类字符串的数量对 109 + 7 进行模运算。

输入

输入的第一行包含单个整数 n (1 ≤ n ≤ 105)。

输入的第二行包含长度为 n 的单个字符串,由字符“ACGT”组成。

输出

打印一个数字——答案以 109 + 7 为模。

示例

输入 #1

1
C

输出 #1

1

输入 #2

2
AG

输出 #2

4

输入 #3

3
TTT

输出 #3

1

注意

请注意,如果对于两个不同的字符串 t1 和 t2,ρ(s, t1) 和 ρ(s, t2) 的值在所有可能的 t 中是最大的,那么在答案中必须考虑这两个字符串,即使其中一个字符串可以通过另一个字符串的循环移位获得。

在第一个样本中,ρ("C", "C") = 1,对于长度为 1 的其余字符串 t,ρ(s, t) 值为 0。

在第二个示例中,ρ(“AG”,“AG”) = ρ(“AG”,“GA”) = ρ(“AG”,“AA”) = ρ(“AG”,“GG”) = 4。

在第三个样本中,ρ("TTT", "TTT") = 27