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 not a 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 the 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.

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:

1. Remove 1^st character: 99b
2. Remove 1^st, 2^nd characters: 9b
3. Remove 1^st, 3^rd characters: 9b
4. Remove 2^nd, 4^th characters: b9
5. Remove 3^rd, 4^th characters: b9
6. Remove 4^th character: b99