Non-Palindromic Permutations

Alice has n characters, all lowercase English letters. They are numbered from \(1\) to \(n\) with letters \(c_1, c_2, \dots, c_n\). Bob wants to rearrange these characters to form a string \(S\) by choosing a permutation \(p_1, p_2, \dots, p_n\) such that \(S = c_{p_1} c_{p_2} \dots c_{p_n}\). Knowing that Alice is a perfectionist, Bob wants to torment her by ensuring that \(S\) is non‐palindromic.

A string is non‐palindromic if and only if it is different from its reverse. For example, the reverse of abcda is adcba so they are different, whereas abcba is a palindrome.

Your task is to determine the number of permutations of \(\{1,2,\dots,n\}\) that yield a non‐palindromic string \(S\). Since the answer can be large, output it modulo \(10^9+7\).

Note: Although the characters may repeat, each permutation is considered distinct because the positions of the characters (their original indices) matter.

inputFormat

The first line of input contains an integer \(n\) (the number of characters). The second line contains a string of length \(n\) consisting of lowercase English letters.

outputFormat

Output a single integer: the number of permutations that form a non‐palindromic string, modulo \(10^9+7\).

sample

2
aa

0