Decomposition

You are given a string $S$. You want to partition it into several (possibly one) nonempty substrings. There are $2^{|S|-1}$ ways of partitions. For example, aba, ab+a, a+ba, a+b+a are all the partitions of the string aba.

The weight of a substring $T$ is the length of the shortest string $x$ such that $T = x x \ldots x$. For example, the weight of aaa is $1$, and the weight of ab is $2$. The weight of a partition is the product of the weights of all substrings in it.

Output the sum of the weights of all partitions, modulo $10^9 + 7$.

The first line contains an integer $T$ ($1 \leq T \leq 10^5$), the number of test cases.

Each test case is on its own line and contains a string $S$ ($1 \leq |S| \leq 2 \cdot 10^5$) made of lowercase English letters. The sum of $|S|$ over all test cases is at most $10^6$.

For each test case, output the answer modulo $10^9 + 7$ on its own line.