给定一个字符串 $S$。你需要将其划分为若干个（可能为一个）非空子串。

划分的方法共有 $2^{|S|-1}$ 种。例如，“aba”、“ab”+“a”、“a”+“ba”、“a”+“b”+“a” 都是字符串“aba”的划分。

我们定义一个子串 $T$ 的权值为满足 $T = xx \dots x$ 的最短字符串 $x$ 的长度。例如，“aaa”的权值为 1，“ab”的权值为 2。我们定义一个划分的权值为该划分中所有子串权值的乘积。

输出所有划分的权值之和。答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 每个测试用例占一行，包含一个由小写英文字母组成的字符串 $S$ ($1 \le |S| \le 2 \cdot 10^5$)。 保证 $\sum |S| \le 10^6$。

输出格式

对于每个测试用例，输出答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

1
abaababaabbbaabbbb

输出 1

5320053