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<= 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
EXAMPLE

INPUT:

2
AA
b99b

OUTPUT:
0
6

EXPLANATION :
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