Description

Recently, the director found that more and more animals in the zoo were lazy and only cared about eating. For example, penguins only act cute to ask visitors for food. To rectify this bad trend and make the animals ask for food with their real skills, the director decided to open an algorithms class so that the animals could learn algorithms.

One day, the director explained the KMP algorithm.

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

Panda: "For the substring formed by the first $i$ characters of string $S$, among the strings that are both its suffix and its prefix (excluding the substring itself), the maximum length is denoted as $\mathrm{next}[i]$."

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

Panda: "For example, if $S$ is $\verb!abcababc!$, then $\mathrm{next}[5] = 2$. This is because the first $5$ characters of $S$ are $\verb!abcab!$, and $\verb!ab!$ is both its suffix and its prefix, and there is no longer string that satisfies this property. Similarly, we can also get $\mathrm{next}[1] = \mathrm{next}[2] = \mathrm{next}[3] = 0$, $\mathrm{next}[4] = \mathrm{next}[6] = 1$, $\mathrm{next}[7] = 2$, $\mathrm{next}[8] = 3$."

The director praised Panda for previewing diligently. Then he explained in detail how to compute the $\mathrm{next}$ array in $O(L)$ time.

Before class ended, the director posed a question: "The KMP algorithm can only compute the $\mathrm{next}$ array. I now want to compute a more powerful array $\mathrm{num}$ — for the substring formed by the first $i$ characters of string $S$, count the number of strings that are both its suffix and its prefix, and moreover the suffix and the prefix do not overlap. Denote this count as $\mathrm{num}[i]$. For example, if $S$ is $\verb!aaaaa!$, then $\mathrm{num}[4] = 2$. This is because the first $4$ characters of $S$ are $\verb!aaaa!$, among which $\verb!a!$ and $\verb!aa!$ both satisfy the property 'being both a suffix and a prefix', while ensuring that the suffix and the prefix do not overlap. Although $\verb!aaa!$ also satisfies 'being both a suffix and a prefix', unfortunately its suffix and prefix overlap, so it cannot be counted. Similarly, $\mathrm{num}[1] = 0, \mathrm{num}[2] = \mathrm{num}[3] = 1, \mathrm{num}[5] = 2$."

Finally, the director announced a reward: the first student to solve it correctly would get a box of chocolates. Hearing this, the penguin who had slept through the class suddenly woke up! But the penguin could not solve the problem, so it asked you, a visitor to the zoo, for help. Can you help the penguin write a program to compute the $\mathrm{num}$ array?

In particular, to avoid massive output, you do not need to print each $\mathrm{num}[i]$. You only need to output the product of all $(\mathrm{num}[i] + 1)$, modulo $10^9 + 7$.

Input Format

The first line contains a single positive integer $n$, the number of test cases.
Then follow $n$ lines, each describing one test case. Each test case contains a single string $S$. See the problem statement for the definition of $S$. It is guaranteed that $S$ contains only lowercase letters. The input file will not contain extra blank lines, and there will be no trailing spaces at the end of lines.

Output Format

Output $n$ lines, each describing the answer for one test case, in the same order as the input. For each test case, output a single integer, which is the answer modulo $10^9 + 7$. The output file should not contain extra blank lines.

3
aaaaa
ab
abcababc

36
1
32 

Hint

Translated by ChatGPT 5