题目描述

Alice 有 n 个字符，它们都是英文小写字母，从 1～n 编号，分别为 c1,c2,…,cn。

Bob 准备将这些字符重新排列，组成一个字符串 S。Bob 知道 Alice 有强迫症，所以他打算将 S 组成一个非回文串来折磨 Alice。

现在 Bob 想知道他共有多少种不同的排列字符的方案，能使得 S 是个非回文串。一种排列字符的方案指的是一个 1～n 的排列 p_i，它所组成的 S=c_{p1}c_{p2}…c_{pn}。

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

由于最后的结果可能很大，你只需要告诉 Bob 总方案数对 $10^{9}+7$ 取模后的值。

输入格式

第一行输入一个整数 $n$。

第二行输入一个长度为 $n$ 的英文小写字母字符串 $S$。

输出格式

输出非回文排列方案数对 $10^9+7$ 取模后的值。

数据范围与约定

对于 20% 的数据，n≤8；

对于 50% 的数据，n≤20；

另有 30% 的数据，字符只包含 a 和 b；

对于 100% 的数据，3≤n≤2000。

可见测试数据

输入数据 1

3
aba

输出数据 1

4

输入数据 2

8
aabbbbcc

输出数据 2

39168

输入数据 3

3
abc

输出数据 3

6