Announcement
**Second Round will be ONLINE instead of ONSITE*****
Problem Statement

Deepanshu often likes to play with palindromes. Today He has a string S which consists of lowercase letters only. Let P[i] be the number of palindromic substring of S having length i.
Deepanshu is interested in finding the value of E, where

As he is having trouble finding it and you are Deepanshu’s best friend, please help him to find the value of E. The value may get very large, print E modulo 1000000007.

INPUT

The First line contains t, the number of test cases.
Each test case consists of a single line having the string S.

OUTPUT

For each test case, output the value of E modulo 10^9+7 in a separate line.

CONSTRAINTS

1 ≤ t ≤ 10

1 ≤ |S| ≤ 100000

SAMPLE INPUT
2
aaa
ab

SAMPLE OUTPUT
10
2

Explanation

In first test case, the there are 3 palindromes of length 1 and two palindromes of length 2 and one palindrome of length 3.
E=13+22+3*1 = 10
Similarly for the case 2.

见题面

见题面