SP13799 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. INPUT : 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 . OUTPUT: Print required answer for each test case in a new line. Since the number can be large print it Modulo 1000000007. CONSTRAINTS 1

N/A

N/A