P5684 [CSP-J2019 江西] 非回文串

Alice 有 $n$ 个字符，它们都是英文小写字母，从 $1 \sim n$ 编号，分别为 $c_1,c_2, \dots , c_n$。 Bob 准备将这些字符重新排列，组成一个字符串 $S$。Bob 知道 Alice 有强迫症，所以他打算将 $S$ 组成一个非回文串来折磨 Alice。 现在 Bob 想知道他共有多少种不同的排列字符的方案，能使得 $S$ 是个非回文串。一种排列字符的方案指的是一个 $1 \sim n$ 的排列 $p_i$，它所组成的 $S = c_{p_1}c_{p_2} \dots c_{p_n}$。 一个字符串是非回文串，当且仅当它的逆序串与原串不同。例如 `abcda` 的逆序串为 `adcba`，与原串不同，故 `abcda` 是非回文串。而 `abcba` 的逆序串与原串相同，是回文串。 由于最后的结果可能很大，你只需要告诉 Bob 总方案数对 $10^9+7$ 取模后的值。

无

无

【数据范围】 对于 $20\%$ 的数据，$n \le 8$； 对于 $50\%$ 的数据，$n \le 20$； 另有 $30\%$ 的数据，字符只包含 `a` 和 `b`； 对于 $100\%$ 的数据，$3 \le n \le 2000$。