A9821 | DNA Alignment

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$ .