Palindromic Anagram

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

inputFormat

input

Input follows the following format.

$S$

outputFormat

output

Output the number on one line.

Examples

Input

ab

Output

0

Input

abba

Output

2

样例

ab

0