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

见题面

见题面