问题 4759 --非回文串

4759: 非回文串

题目描述

  

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$ 取模后的值。

输入

第一行一个正整数 $n$ 表示字符个数。

第二行 $n$ 个英文小写字母 $c_i$。

输出

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

样例输入输出

输入#1 复制
3
aba
输出#1 复制
4
输入#2 复制
8
aabbbbcc
输出#2 复制
39168

提示

对于 $20\%$ 的数据,$n \le 8$;

对于 $50\%$ 的数据,$n \le 20$;

另有 $30\%$ 的数据,字符只包含 "a" 和 "b";

对于 $100\%$ 的数据,$3 \le n \le 2000$。

序号 标题 作者 发表时间 费用 订购数 操作