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