According to a very famous web site, which in this case we will trust, defines a palindrome as ‘a word, phrase, verse, or sentence that reads the same backward or forward’. For example, the phrase A man, a plan, a canal, Panama! is a palindrome. Actually, writing texts consisting of only palindromes is part of a literary technique called constrained writing.

Now imagine the wise Yoda, the master of all, whose proficiency putting words together in sentences is one of his well-known abilities. He is now interested in enriching his long- lasting, and maybe boring, inactivity periods by ‘composing’ palindromic sentences. That is, he has plans to use only palindromic sentences for his chats. For this matter, he needs to practice. The first task in his practice plan is to count all the palindromes that can be arranged out of a collection of characters.

Today, you will be Yoda’s assistant for this first task. Your only mission is to, given a sequence of characters, determine how many palindromes can be obtained with some of the characters in the sequence; you will only take into account uppercase or lowercase letters. Put in other way, you need to determine how many permutations of a give sequence of characters are palindromes. Your solution will help definitively master Yoga.

Input

The input consists of several test cases, one per line. For each test case, the input consist of a sequence of ASCII characters.

Output

For each test case you should print in a single line, and according to the order of the test cases, the total number of palindromes generated by the input sequence of ASCII characters. For your purpose, you should only consider uppercase or lowercase characters appearing in the input; any other character should be ignored in the calculations. Uppercase and lowercase characters are not considered different; for example, A and a should not be considered different. In any case, the total number of palindromes will not exceed the number e⁴³ , where e is approximately 2.71828. Remember that the empty sequence is a palindrome itself.

Example

Input:
A man, a plan, a canal, Panama!
arD,R!A
B.a.C1/
12[’;. =1

Output:
15120
2
0
1