Description

Alice has $n$ characters, all of which are lowercase English letters, numbered from $1 \sim n$, namely $c_1,c_2, \dots , c_n$.
Bob plans to rearrange these characters to form a string $S$. Bob knows that Alice has OCD, so he plans to make $S$ a non-palindromic string to annoy Alice.

Now Bob wants to know how many different ways of rearranging the characters there are such that $S$ is a non-palindromic string. A rearrangement plan means a permutation $p_i$ of $1 \sim n$, and it forms $S = c_{p_1}c_{p_2} \dots c_{p_n}$.

A string is non-palindromic if and only if its reversed string is different from the original string. For example, the reversed string of abcda is adcba, which is different from the original string, so abcda is a non-palindromic string. However, the reversed string of abcba is the same as the original string, so it is a palindromic string.

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

Input Format

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

Output Format

Only one line containing an integer representing the answer. The answer is taken modulo $10^9+7$.

3
aba

4

8
aabbbbcc

39168

Hint

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

Translated by ChatGPT 5