题目描述

ZKX有 $n$ 个字符，它们都是英文小写字母，从 $1 \sim n$ 编号，分别为 $c_1,c_2, \dots , c_n$，ZSH准备将这些字符重新排列，组成一个字符串 $S$，ZSH知道ZKX有强迫症，所以他打算将 $S$ 组成一个非回文串来折磨ZKX

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

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

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

输入格式

第一行一个正整数 $n$ 表示字符个数。
第二行 $n$ 个英文小写字母 $c_i$。
$3 \le n \le 10^{5}$

输出格式

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

样例

3
aba

4

8
aabbbbcc

39168

样例$1$解释:
S=aba a=$c_{1}$, b=$c_{2}$,a=$c_{3}$
$aab$ $\longrightarrow$ $c_1,c_3,c_2$
$aab$ $\longrightarrow$ $c_3,c_1,c_2$
$baa$ $\longrightarrow$ $c_2,c_1,c_3$
$baa$ $\longrightarrow$ $c_2,c_3,c_1$