@ykj59

Vasya对生物信息学产生了兴趣。他打算写一篇关于相似的环状DNA序列的文章，所以他发明了一种确定环状序列相似性的新方法。 假设字符串 s 和 t 的长度 n 

相同，则函数 h（s， t） 定义为 s 和 t 的相应符号相同的位置数。函数 h（s， t） 可用于定义 Vasya 距离 ρ（s， t） 的函数：

其中，通过应用左圆移 i 次从字符串 s 获得。例如 ρ（“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 的字符串。现在他想数一数有多少根字符串 t 使得与字符串 s 的 Vasya 

距离达到最大可能值。从形式上讲，t 必须满足等式： ρ（s， t）=max p(s,u)(u:|u|=|s|)。 瓦夏无法尝试所有可能的字符串来找到答案，所以他需要你的帮

助。由于答案可能非常大，因此计算此类字符串的数目模 10^9 + 7。 输入 输入的第一行包含单个整数 n （1 ≤ n ≤ 105）。 输入的第二行包含长度为 n 的单

个字符串，由字符“ACGT”组成。 输出 打印一个数字 — 答案模 10^9 + 7。

注意 

请注意，如果对于两个不同的字符串 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