Problem Description

Alice has $n$ characters, all of which are lowercase English letters, numbered from $1$ to $n$, denoted as $c_1, c_2, \dots, c_n$.
Bob plans to rearrange these characters to form a string $S$. Knowing that Alice has obsessive-compulsive disorder, Bob intends to make $S$ a non-palindrome string to torment Alice.

Now, Bob wants to know how many different ways he can rearrange the characters to make $S$ a non-palindrome string. A way to rearrange the characters is a permutation of $1$ to $n$, denoted as $p_i$, which forms $S = c_{p_1}c_{p_2} \dots c_{p_n}$.

A string is a non-palindrome if and only if its reverse is different from the original string. For example, abcda is a non-palindrome because its reverse is adcba, which is different from the original string. However, abcba is a palindrome because its reverse is the same as the original string.

Since the final result may be very large, you only need to tell Bob the total number of ways modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$ representing the number of characters.
The second line contains $n$ lowercase English letters $c_i$.

Output Format

Output a single integer representing the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
aba

Sample Output #1

4

Sample Input #2

8
aabbbbcc

Sample Output #2

39168

Notes

Data Range

For $20\%$ of the data, $n \le 8$;
For $50\%$ of the data, $n \le 20$;
For another $30\%$ of the data, the characters only include a and b;
For $100\%$ of the data, $3 \le n \le 2000$.

见题面 Input 部分

见题面 Output 部分