Description

设 $s = s_1 s_2 \cdots s_n$ 是一个长度为 $n$ 的字符串。对于任意 $1$ 到 $n$ 之间的整数 $i$，$s$ 的第 $i$ 个后缀定义为 $s_i s_{i+1} \cdots s_n$。例如，“contest” 的第 $4$ 个后缀是 “test”，而 “suffix” 的第 $1$ 个后缀就是 “suffix” 本身。

可以考虑 $s$ 的字典序最小后缀。设第 $k$ 个后缀在 $s$ 的所有后缀中字典序最小，方便起见，我们称这样的 $k$ 为 $s$ 的最小下标（minimum index）。

给定一个字符串 $s = s_1 s_2 \cdots s_n$，你的任务是计算：

$$\sum_{i=1}^{n} \left( s_1 s_2 \cdots s_i \text{ 的最小下标} \right) \cdot 1112^{\,n-i}$$

这个值可能非常大，你只需要输出它对 $10^9+7$ 取模的结果。

Format

Input

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试数据的组数。接下来 $t$ 行，每行包含一个非空的、仅由小写英文字母组成的字符串。所有测试数据的字符串总长度不超过 $10^6$。

Output

对于每组测试数据，输出一行一个整数，表示答案。

Samples

1
aab

1238769

Hint

“a”、“aa”、“aab” 的最小下标分别为 $1, 2, 1$。所以答案为

$$\left(1 \cdot 1112^2 + 2 \cdot 1112 + 1 \right) \bmod (10^9+7) = 1238769$$