Minimum Index

Let s=$s_1$ $s_2$$ \cdots $$s_n$ be a string of length n. For any integer k between 1 to n, the $k^{th}$ suffix of s is defined as $s_k$ $s_{k+1}$$ \cdots $$s_n$. For example, the $4^{th}$ suffix of “contest” is “test” and the $1^{st}$ suffix of “suffix” is “suffix” itself.

One can consider lexicographically smallest suffix of s. Let the $k^{th}$ suffix is lexicographically minimum among all suffixes of s. Conveniently, let’s call such k minimum index of s. Given a string t=$t_1$ $t_2 \cdots t_n$, your task is to calculate the sum of (minimum index of $t_1$ $t_2 \cdots t_i$)$ \cdot 1112^{i-1}$ over all i=1,2,3,$ \cdots $,n. This value may be too large, you are only required to print it modulo $10^9$+7.

The first line of the input contains a single integer T (1≤T≤10 000), the number of test cases. Each of the next T lines contains a non-empty string with at most $10^6$ lowercase English letters. The total length of the input string over all test cases doesn’t exceed $2 \cdot 10^7$.

For each test case, you should print the answer in a single line.