UCalgary Competitive Programming Week 12

Start

2021-11-26 13:21 AKST

UCalgary Competitive Programming Week 12

End

2021-12-03 13:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -56 days 1:59:11

Time elapsed

167:39:00

Time remaining

0:00:00

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$.

Sample Input 1 Sample Output 1
5
bob
a
aa
aaa
abcdb
5
1
3
7
8