Palindrome row

Ksyusha has a string (s) and she enjoys rearranging its letters. She is curious to find out how many distinct palindromes she can create by rearranging the letters of (s).

A palindrome is a string that reads the same forwards and backwards. For instance, the string "ded" is a palindrome.

Input

The input consists of a single line containing the string (s) ((1 $\le$ |s| $\le$ 20)), which is composed solely of lowercase Latin letters.

Output

Output a single integer representing the number of unique palindromes Ksyusha can form by rearranging the letters of the string (s).

Note. A string (x = x_1x_2...x_p) is considered lexicographically smaller than a string (y = y_1y_2...y_q) if either (p < q) and (x_1 = y_1), (x_2 = y_2), ..., (x_p = y_p), or there exists an index (r) ((r < p), (r < q)) such that (x_1 = y_1), (x_2 = y_2), ..., (x_r = y_r) and (x_r+1 < y_r+1). The characters of the strings are compared based on their ASCII values.

Examples