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 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 1st character: 99b
  2. Remove 1st, 2nd characters: 9b
  3. Remove 1st, 3rd characters: 9b
  4. Remove 2nd, 4th characters: b9
  5. Remove 3rd, 4th characters: b9
  6. Remove 4th character: b99

Added by:smit hinsu
Date:2013-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 13 , own problem

hide comments
2018-06-17 15:45:00
As the other comments say .pretty easy.Think simple .Dont complicate
2018-01-29 10:01:57 ingeniosus
Unbelievably easy. Try not to complicate stuff.
2014-04-03 06:51:11 Arika Saputro
the solution is simple, don't get trapped on combination solution ;D
2013-02-19 16:48:47 Ehor Nechiporenko
If you resolve problem correctly, you will understand, why exactly Loki was Naive :-))))))))

Last edit: 2013-02-19 16:49:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.