NAIVELOK - Naive Loki
Loki has succeeded in his devilish scheme and opened the portal to Asgard to summon his army to earth.
To protect earth from this predicament, Iron Man must find a way to close this portal. He notices that the passcode on the portal is a palindromic string S. Also no character in this string occurs more than 2 times. Iron man can remove any number of characters from this string. Genius that he is, he deduces that the portal will close whenever the string is a non-palindrome. But that is too easy for him. So he waits and wonders how many different ways there are to achieve this. Two ways are considered different if there exists an i such that character at index i is removed in one way and not removed in another.
The first line of input contains a single line T, which represents the number of test cases. Then T lines will follow, and each contains a palindromic string S .
Print required answer for each test case in a new line. Since the number can be large print it Modulo 1000000007.
1<= T <=1000
1<= |S| <= 100 ,where |S| represents the length of the string S.
The string S is case sensitive, and will contain only characters in the range [a-z], [A-Z], [0-9].
There would be at most two positions in S which will contain same character .
Memory Limit : 32MB
Time Limit : 1second
In the first sample case there is no way in which string can be converted to non-palindrome .
In the second sample case there are 6 ways to convert string to non-palindromic namely ,
i) Remove 1st character : 99b
ii) Remove 1st, 2nd characters : 9b
iii) Remove 1st, 3rd characters : 9b
iv) Remove 2nd, 4th characters : b9
v) Remove 3rd, 4th characters : b9
vi) Remove 4th character : b99
the solution is simple, don't get trapped on combination solution ;D
If you resolve problem correctly, you will understand, why exactly Loki was Naive :-))))))))Last edit: 2013-02-19 16:49:33