#P5684. [CSP-J2019 江西] 非回文串
[CSP-J2019 江西] 非回文串
题目描述
Alice 有 个字符,它们都是英文小写字母,从 编号,分别为 。
Bob 准备将这些字符重新排列,组成一个字符串 。Bob 知道 Alice 有强迫症,所以他打算将 组成一个非回文串来折磨 Alice。
现在 Bob 想知道他共有多少种不同的排列字符的方案,能使得 是个非回文串。一种排列字符的方案指的是一个 的排列 ,它所组成的 。
一个字符串是非回文串,当且仅当它的逆序串与原串不同。例如 abcda
的逆序串为 adcba
,与原串不同,故 abcda
是非回文串。而 abcba
的逆序串与原串相同,是回文串。
由于最后的结果可能很大,你只需要告诉 Bob 总方案数对 取模后的值。
输入格式
第一行一个正整数 表示字符个数。
第二行 个英文小写字母 。
输出格式
仅一行一个整数表示答案。答案对 取模。
3
aba
4
8
aabbbbcc
39168
提示
【数据范围】
对于 的数据,;
对于 的数据,;
另有 的数据,字符只包含 a
和 b
;
对于 的数据,。