非回文串

• 时间限制：1 秒
• 内存限制：128 MiB
• 输入：标准输入
• 输出：标准输出

题目描述

Alice 有 $n$ 个字符，它们都是英文小写字母，从 $1$ 到 $n$ 编号，分别为 $c_1,c_2,\ldots,c_n$。

Bob 选择 $1$ 到 $n$ 的一个排列 $p$，组成字符串

Bob 希望 $S$ 不是回文串。请计算有多少个排列 $p$ 能满足要求，并将答案对 $10^9+7$ 取模。

注意：字符按编号区分。即使两个编号上的字母相同，交换这两个编号也会得到不同的排列方案。

输入格式

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

第二行一个长度为 $n$、仅由英文小写字母组成的字符串，第 $i$ 个字符为 $c_i$。

输出格式

输出一个整数，表示非回文排列方案数对 $10^9+7$ 取模的结果。

样例输入 1

3
aba

样例输出 1

4

样例输入 2

8
aabbbbcc

样例输出 2

39168

数据范围

对于所有数据，$3\le n\le 2000$。