DNA Alignment

题意翻译

给定一个n长度的由$A$、$C$、$G$、$T$四种序列构成的$DNA$序列。问有多少种方案，构造另一种序列，使得两种序列在$shift$过程中，两者相同的位数总和最大。$shift$操作即移位操作，两者分别移动，然后求相同位的个数。

题目描述

Vasya became interested in bioinformatics. He's going to write an article about similar cyclic DNA sequences, so he invented a new method for determining the similarity of cyclic sequences. Let's assume that strings $ s $ and $ t $ have the same length $ n $ , then the function $ h(s,t) $ is defined as the number of positions in which the respective symbols of $ s $ and $ t $ are the same. Function $ h(s,t) $ can be used to define the function of Vasya distance $ ρ(s,t) $ :  where  is obtained from string $ s $ , by applying left circular shift $ i $ times. For example, $ ρ("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 found a string $ s $ of length $ n $ on the Internet. Now he wants to count how many strings $ t $ there are such that the Vasya distance from the string $ s $ attains maximum possible value. Formally speaking, $ t $ must satisfy the equation: . Vasya could not try all possible strings to find an answer, so he needs your help. As the answer may be very large, count the number of such strings modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ). The second line of the input contains a single string of length $ n $ , consisting of characters "ACGT".

输出格式

Print a single number — the answer modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

1
C

输出样例 #1

1

输入样例 #2

2
AG

输出样例 #2

4

输入样例 #3

3
TTT

输出样例 #3

1

说明

Please note that if for two distinct strings $ t_{1} $ and $ t_{2} $ values $ ρ(s,t_{1}) $ и $ ρ(s,t_{2}) $ are maximum among all possible $ t $ , then both strings must be taken into account in the answer even if one of them can be obtained by a circular shift of another one. In the first sample, there is $ ρ(&quot;C&quot;,&quot;C&quot;)=1 $ , for the remaining strings $ t $ of length 1 the value of $ ρ(s,t) $ is 0. In the second sample, $ ρ(&quot;AG&quot;,&quot;AG&quot;)=ρ(&quot;AG&quot;,&quot;GA&quot;)=ρ(&quot;AG&quot;,&quot;AA&quot;)=ρ(&quot;AG&quot;,&quot;GG&quot;)=4 $ . In the third sample, $ ρ(&quot;TTT&quot;,&quot;TTT&quot;)=27 $