p01473 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
```python
import collections
from math import *
s=input()
a=collections.Counter(s)
o=0
for x in a:
    if a[x]&1:
        o+=1
        if o>1:print(0);break
        a[x]-=1
else:
    b=factorial(len(s)//2)
    for x in a.values():
        b//=factorial(x//2)
    print(b)
```