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

[CSP-J2019 江西] 非回文串

题目描述

Alice 有 nn 个字符,它们都是英文小写字母,从 1n1 \sim n 编号,分别为 c1,c2,,cnc_1,c_2, \dots , c_n
Bob 准备将这些字符重新排列,组成一个字符串 SS。Bob 知道 Alice 有强迫症,所以他打算将 SS 组成一个非回文串来折磨 Alice。

现在 Bob 想知道他共有多少种不同的排列字符的方案,能使得 SS 是个非回文串。一种排列字符的方案指的是一个 1n1 \sim n 的排列 pip_i,它所组成的 S=cp1cp2cpnS = c_{p_1}c_{p_2} \dots c_{p_n}

一个字符串是非回文串,当且仅当它的逆序串与原串不同。例如 abcda 的逆序串为 adcba,与原串不同,故 abcda 是非回文串。而 abcba 的逆序串与原串相同,是回文串。

由于最后的结果可能很大,你只需要告诉 Bob 总方案数对 109+710^9+7 取模后的值。

输入格式

第一行一个正整数 nn 表示字符个数。
第二行 nn 个英文小写字母 cic_i

输出格式

仅一行一个整数表示答案。答案对 109+710^9+7 取模。

3
aba
4
8
aabbbbcc
39168

提示

【数据范围】
对于 20%20\% 的数据,n8n \le 8
对于 50%50\% 的数据,n20n \le 20
另有 30%30\% 的数据,字符只包含 ab
对于 100%100\% 的数据,3n20003 \le n \le 2000