P5684 [CSP-J 2019 Jiangxi] Non-palindromic String

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

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

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

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