Problem G
Palindromic Naming

Yraglac is expecting to have a child in the near future. Being a mathematically-minded person, he would like his child’s name to be a palindrome – that is, reads the same when read forward and backward. Given a name, he would like to count the number of ways he can create a palindromic name by removing zero or more letters. For example, given the name “abcdb”, he can remove the letters “a” and “c” to get the palindrome “bdb”. Of course, the resulting name must not be empty. The answer might be very large so you should output the answer modulo $1\, 000\, 000\, 007 = 10^9 + 7$.

Input

The first line contains a single integer $T \leq 10$ giving the number of test cases. Each test case consists of a single name with length between $1$ and $2\, 000$ inclusive, containing only lowercase letters.

Output

For each test case, output a single line containing the answer modulo $1\, 000\, 000\, 007$.

5
bob
a
aa
aaa
abcdb

5
1
3
7
8