T564090 「2025 YAC Round 2」帕琪不希望发生的事

「2025 YAC Round 2」G 题

帕秋莉有 $n$ 个符文 $c_1, c_2, \ldots, c_n$，这些符文都是小写英文字符。现在她想要将这些所有的符文组合起来变成一个字符串 $s$。 但是，如果组成的字符串 $s$ 是一个 **回文串**，那么符文的 **魔力会抵消**。帕秋莉不希望发生魔力抵消这件事。 帕秋莉想知道有多少种不同的排列字符的方案，使得字符串 $s$ **不会** 发生魔力抵消。 一种排列字符的方案指：一个仅包含数字 $1 \sim n$ 且每个数字恰好出现一次的排列 $p$，组成一个字符串 $s = c_{p_1}c_{p_2}\ldots c_{p_n}$。 最终答案可能很大，你需要将答案对 $10^9 + 7$ 取模。

第一行输入一个整数 $n$（$3 \le n \le 2000$），表示符文个数。 第二行输入 $n$ 个英文小写字符 $c_1,c_2,\ldots,c_n$。

输出一行一个整数表示答案。答案对 $10^9+7$ 取模。