Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given a string P of length N. A string is called palindromic if it reads the same forward and backward. A palindromic string has even length if its length is a positive even number.

For any two even-length palindromic strings S and T, in a single operation, you can do one of the following operations on either S or T:

• Extend: Add the same character at the front and back of the string.
• Shrink: Remove the first and last character of the string.

The distance between two even-length palindromic strings S and T is defined as the minimum number of operations required to make S equal to T. It is always possible to make such two palindromic strings equal by performing a finite number of these operations.

Your task is to calculate the sum of distances between all unordered pairs of even-length palindromic substrings of P. As this number can be very large, output it modulo 1000000007.

Note that

• Each occurrence of an even-length palindromic substring is considered distinct, even if the substring is identical. For example, if the substring "aa" appears at indices 1-2 and 3-4, these are treated as two distinct substrings in the calculation.
• An unordered pair (S,T) means that (S,T) and (T,S) are considered the same and should only be counted once.

Input

The first line contains a single integer T (1 <= T <= 100) - the number of test cases.

Each test case contains a single line with a string P of length N (1 <= N <= \(3 * 10^5\)) consisting of lowercase English letters only.

It is guaranteed that the sum of N over all test cases does not exceed \(3 * 10^5\).

Output

For each testcase, print a single integer, the sum of distances for all unordered pairs of even-length palindromic substrings of P. As this number can be very large, output it modulo 1000000007.

Sample

2
abba
aaaa

1
3

In the first test case, there are 2 even-length palindromic substrings in P, "bb" and "abba". So, the answer is the distance between "bb" and "abba". We can, for example, apply 1 Shrink operation on "abba" to make it "bb". So, the distance between them is 1.

In the second test case, there are 4 even-length palindromic substrings in P.

• "aa" (at indices 1-2)
• "aa" (at indices 2-3)
• "aa" (at indices 3-4)
• "aaaa" (at indices 1-4)