I. Anapalindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Long ago, in a kingdom of words, there was a librarian who loved palindromes. Whenever she found a scroll of letters, she tried to cut it into pieces so that each piece could be rearranged into a palindrome. She called such magical pieces AnapalinDromes. For example, the piece "aabb" is an AnapalinDrome as it could be rearranged to "abba", which is a palindrome. Similarly, "a", "aa", and "aba" are AnapalinDromes.

Now she has given you a scroll written as a string $$$s$$$. Your task is to help her count the following:

  • Consider all possible ways to partition the string into one or more contiguous substrings, such that every substring is an AnapalinDrome.
  • The score of a partition is the number of substrings in it.
  • You must find the sum of scores over all valid partitions.

Since the number can be large, output it modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ — the number of test cases. Each of the next $$$t$$$ lines contains a string $$$s$$$ consisting of lowercase English letters.

  • $$$1 \le t \le 10^5$$$
  • $$$1 \le |s| \le 10^5$$$
  • The total length of all strings across all test cases does not exceed $$$10^5$$$.
  • Strings consist of lowercase English letters only.
Output

For each test case, print a single integer - the sum of scores of all valid partitions of the string, modulo $$$10^9 + 7$$$.

Example
Input
2
aab
abc
Output
6
3
Note
  • For $$$s = \texttt{aab}$$$: the valid partitions are:
    • aab $$$\rightarrow$$$ score = 1
    • aa | b $$$\rightarrow$$$ score = 2
    • a | a | b $$$\rightarrow$$$ score = 3
    Total = $$$1 + 2 + 3 = 6$$$.
  • For $$$s = \texttt{abc}$$$: the only valid partition is a | b | c with score = 3.