Recently, the zoo director noticed that more and more animals in the zoo are becoming lazy. For example, penguins only know how to act cute to beg for food from tourists. To rectify the bad atmosphere in the zoo and encourage the animals to earn their food through their own genuine skills, the director decided to set up an algorithm class for the animals to learn algorithms.

One day, the director explained the KMP algorithm to the animals.

Director: "For a string $S$ of length $L$, we can compute an array called next in $O(L)$ time. Has anyone previewed the meaning of the next array?"

Panda: "For the substring consisting of the first $i$ characters of string $S$, the length of the longest string that is both a suffix and a prefix (excluding the string itself) is denoted as next[i]."

Director: "Very good! Can you give an example?"

Panda: "For example, if $S$ is abcababc, then next[5]=2. Because the first 5 characters of $S$ are abcab, ab is both its suffix and prefix, and no longer string satisfies this property. Similarly, we can obtain next[1] = next[2] = next[3] = 0, next[4] = next[6] = 1, next[7] = 2, next[8] = 3."

The director praised the diligent Panda. Subsequently, he explained in detail how to compute the next array in $O(L)$ time.

Before the end of the class, the director posed a question: "The KMP algorithm can only compute the next array. Now I want to compute a more powerful num array—for the substring consisting of the first $i$ characters of string $S$, the number of strings that are both a suffix and a prefix, and where the suffix and prefix do not overlap, is denoted as num[i]. For example, if $S$ is aaaaa, then num[4] = 2. This is because the first 4 characters of $S$ are aaaa, where both a and aa satisfy the property of being 'both a suffix and a prefix', while ensuring that this suffix and this prefix do not overlap. Although aaa satisfies the property of being 'both a suffix and a prefix', unfortunately, this suffix and this prefix overlap, so it cannot be counted. Similarly, num[1] = 0, num[2] = num[3] = 1, num[5] = 2."

Finally, the director offered a reward: the first student to solve it gets a box of chocolates. Hearing this, the penguin, who had been sleeping for the whole class, woke up immediately! But the penguin didn't know how to solve this problem, so it asked you, who are visiting the zoo, for help. Can you help the penguin write a program to compute the num array?

Specifically, to avoid a large amount of output, you do not need to output the values of num[i]. You only need to output the result of: $$\prod_{i=1}^{L} (\text{num}[i] + 1) \pmod{1,000,000,007}$$ where $\prod_{i=1}^{L} (\text{num}[i] + 1) = (\text{num}[1] + 1) \times (\text{num}[2] + 1) \times \dots \times (\text{num}[L] + 1)$.

Input

The first line contains a single positive integer $n$, representing the number of test cases. Each of the following $n$ lines describes a test case. Each test case contains only a single string $S$. The definition of $S$ is detailed in the problem description. It is guaranteed that $S$ contains only lowercase letters.

Output

For each test case, output a single integer representing the answer modulo $1,000,000,007$.

Examples

Input 1

3
aaaaa
ab
abcababc

Output 1

36
1
32

Input 2

See zoo/zoo.in and zoo/zoo.ans in the contestant directory.

Constraints

The ranges and characteristics of all test cases are shown in the table below: