Solve the programming task below in a Python markdown code block.
Problem statement

Given the string $ S $. Find the number of all anagrams in $ S $ that are palindromic.

An anagram of the string $ X $ is an anagram of $ Y $, which means that $ X $ is equal to $ Y $, or that the rearranged characters of $ X $ are equal to $ Y $. For example, for the string abcd, abcd and cbda are anagrams, but abed, cab and abcdd are not anagrams.

When the string $ X $ is a palindrome, it means that the reverse reading of $ X $ is equal to $ X $ itself. For example, abc and ab are not palindromes, and a and abccba are palindromes.

Constraint

* $ 1 \ leq | S | \ leq 40 $ ($ | S | $ is the length of the string $ S $)
* $ S $ contains only lowercase letters.
* The answer is guaranteed to be less than $ 2 ^ {63} $.



input

Input follows the following format.


$ S $

output

Output the number on one line.

Examples

Input

ab


Output

0


Input

abba


Output

2