National Olympiad in Informatics, China, 2014

Recently, the zookeeper noticed that number of all-eat and no-work animals have been increasing. Take penguins for example – they only care about getting food from the zoo's visitors by showing off their cuteness alone. To fix the bad vibe around the zoo and to ensure that animals only get food via exhibiting their true talents, the zookeeper has decided to set up an algorithms class to teach algorithms to the animals.

One day, the zookeeper decided to lecture the KMP algorithm to the animals.

Zookeeper: "For a given string $S$ of length $L$, we can construct an array $\mathrm{next}[]$ in running time $\mathcal{O}(L)$. Can anybody guess the meaning of $\mathrm{next}[]$?

Panda: "Within the first $i$ characters of string $S$, the length of the longest substring (excluding itself) that is both its prefix and suffix will be stored in $\mathrm{next}[i]$."

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

Panda: "If $S=$ abcababc, then $\mathrm{next}[5]=2$. This is because the first 5 characters is abcab, and ab is both its prefix and suffix, and a longer substring with this property does not exist. Likewise, we can find that $\mathrm{next}[1]=\mathrm{next}[2]=\mathrm{next}[3]=0$, $\mathrm{next}[4]=\mathrm{next}[6]=1$, $\mathrm{next}[7]=2$, and $\mathrm{next}[8]=3$."

The zookeeper commended Panda's studiousness. Then, he carefully explained how $\mathrm{next}[]$ could be computed in $\mathcal{O}(L)$.

Before dismissing the class, the zookeeper posed a problem: "The KMP algorithm can only generate the array $\mathrm{next}[]$. We wish to obtain an even more powerful $\mathrm{num}[]$ array – within the first $i$ characters of string $S$, the number of substrings that is both its prefix and suffix, and that the prefix and suffix does not overlap, will be stored in $\mathrm{num}[i]$. For example, if $S=$ aaaaa, then $num[4]=2$. This is because for the first 4 characters of $S$, aaaa, substrings a and aa each satisfy the conditions of 'being both a prefix and suffix,' as well as guaranteeing that the prefix and suffix do not overlap. Although substring aaa does satisfy the condition of 'being both a prefix and suffix,' we cannot count it because as simultaneously a prefix and suffix of aaaa, it overlaps with itself. By the same reasoning, we can see that $\mathrm{num}[1]=0$, $\mathrm{num}[2]=\mathrm{num}[3]=1$, and $\mathrm{num}[5]=2$."

Finally, the zookeeper designated a prize. The first student to solve this will be rewarded a box of chocolates. After hearing this, Penguin, who has been sleeping for the entire class, has immediately awoken! But Penguin doesn't have a clue how to solve this problem. So, he has scoured the entire zoo to find you for help. Can you help Penguin write a program to compute the $\mathrm{num}[]$ array?

Specifically, to avoid huge amounts of output, you do not have to output each value of $\mathrm{num}[i]$. Instead, you will only have to output $[\prod _{i=1}^L(\mathrm{num}[i]+1)]mod1000000007$. Here, $\prod _{i=1}^L(\mathrm{num}[i]+1)=(\mathrm{num}[1]+1)\times (\mathrm{num}[2]+1)\times \cdots \times (\mathrm{num}[L]+1)$.

Input Specification

The first line of input contains a single integer $n$, representing the number of test cases.
For the next $n$ lines, each line will describe one instance of the problem. Each instance will consist of the single string $S$. It is guaranteed that $S$ will only consist of lowercase letters.
The input will not contain extra or trailing spaces.

Output Specification

The output should contain $n$ lines, with each line being the answer to the corresponding input string. The order of the answers should be the same as the order of the strings in the input. For each string, the answer should be a single integer representing the answer modulo $1000000007$.

Sample Input

3
aaaaa
ab
abcababc

Sample Output

36
1
32

Constraints

The constraints of all the test cases are outlined below.

Test Case	Constraints
1	$n\le 5$, $L\le 50$
2	$n\le 5$, $L\le 200$
3	$n\le 5$, $L\le 200$
4	$n\le 5$, $L\le 10000$
5	$n\le 5$, $L\le 10000$
6	$n\le 5$, $L\le 100000$
7	$n\le 5$, $L\le 200000$
8	$n\le 5$, $L\le 500000$
9	$n\le 5$, $L\le 1000000$
10	$n\le 5$, $L\le 1000000$

Problem translated to English by Alex.