Unique Palindromes Count

Given a string s consisting of lowercase English letters, determine the number of unique palindrome strings that can be formed by rearranging all the characters of s exactly once.

A palindrome is a string that reads the same forwards and backwards. A necessary and sufficient condition for the formation of a palindrome is that at most one character appears an odd number of times. Mathematically, if the frequency of each character is given and if half-length is defined as \( n = \sum_{i} \frac{c_i}{2} \), then the number of unique palindromes is computed by:

$$\frac{n!}{\prod_{i} (\frac{c_i}{2})!}$$

For example, for s = "aabb", the two possible unique palindromes are abba and baab, so the answer is 2.

inputFormat

The input consists of a single line containing a non-empty string s composed only of lowercase English letters.

outputFormat

Output a single integer representing the number of unique palindromes that can be formed by rearranging all the characters of s.

aab

1