在魔法世界中，Alice 拥有 n 个神秘字符，每个字符都是英文小写字母，从 1 \sim n 编号，分别为 c_1, c_2, \dots, c_n。

Bob 打算用这些字符组成一个字符串 S，但他想故意惹恼有强迫症的 Alice，因此决定让 S 成为一个非回文串。

所谓非回文串，是指该字符串的逆序与原串不同。

例如，`abcda` 的逆序是 `adcba`，二者不同，因此 `abcda` 是非回文串；而 `abcba` 的逆序与原串相同，是回文串。

Bob 想知道有多少种不同的排列方式，可以使组成的字符串 S 成为非回文串。排列方式的总数可能很大，你只需输出其对 10^9+7 取模后的结果。

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

第二行：n 个英文小写字母，表示每个字符。

一行整数，表示满足条件的排列方式数目对 10^9+7 取模的结果。

样例1解释：

所有可能的排列方式有6种：`aba`, `aab`, `baa`, `baa`, `aba`, `aab`。其中，`aba` 和 `aba` 是回文串，因此非回文串的排列方式有4种。

数据范围

| 数据规模 | 占比 | 具体限制 |

|----------|------|----------|

| 20%      |      | n \le 8 |

| 50%      |      | n \le 20 |

| 30%      |      | 字符只包含 `a` 和 `b` |

| 100%     |      | 3 \le n \le 2000 |