YODA - Yoda Goes Palindromic !

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^43 , 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

Added by:Daniel Gómez Didier
Date:2008-11-18
Time limit:3.950s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:2007 U.Nacional - Circuito de Maratones ACIS / REDIS

hide comments
2015-05-15 22:31:40 Naman Goyal
Really good problem. I solved it with some combinatorics but calculating the term without overflowing and with basic C++ datatype was interesting.
2015-01-16 12:33:44 (Tjandra Satria Gunawan)(曾毅昆)
Both RAJDEEP GUPTA's comments and problem description is right, got AC with both considering digits and not considering digits. I got 3 WAs before because I didn't handle the '\t' in the input. (I use getchar_unlocked, not gets)..
2012-01-27 14:32:53 Paul Redman
The problem description is correct, not the comments: ignore digits, 0-length sequence should give answer 1.
2012-01-16 19:00:30 rishabh
answer for "[ ]" is 1, for an empty string is also 1.
take care of that.
2012-01-12 08:35:28 RAJDEEP GUPTA
please note the following:
1. take input as while(gets(string))
2.you must consider digits too. Answer for "aa11Bbb" is 6.
3. characters other than alphabets and digits should be ignored. Answer for "[]" is 0.
2012-01-02 21:15:46 Prakhar Jain
output for abaaba is 3...


Last edit: 2012-01-02 21:23:29
2011-08-27 17:56:27 biQar
@Prabakaran - u should read input until the END OF FILE.
2011-08-27 17:55:11 biQar
@SpojDog - in the 2nd test case "arD,R!A" we got the string "arDRA". As, this is not case sensitive, we can consider "ardra". Among all the permutations of this string, "ardra" & "radar" ar palindromic !! so the ans is 2.
2011-01-09 07:42:24 Prabakaran
how to end the input?
2010-09-08 21:39:11 যোবায়ের
please at least explain case 2 :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.