题目描述

LJJ 拿到了一串来自火星的字符串。

字符串中，每个字符都是一种火星字母，LJJ 将其转换为小写英文字母 \texttt{a}\sim\texttt{z}，为了便于发现其中的奥秘。

仔细看，这个字符串杂乱中带着有序，有许多重复的片段。于是，LJJ 请来了作为字符串分析专家的你，来帮他分析计算这个字符串的神秘度。

设 (n) 是这个字符串的长度。设 (S[i,j]) 表示字符串 (S) 中第 (i) 个位置到第 (j) 个位置的连续子串（字符串下标从 1 开始）。

若 (i,j,\text{len}) 同时满足：

• (1\leqslant i<j\leqslant i+\text{len}-1<j+\text{len}-1\leqslant n)
• (S[i,i+\text{len}-1]=S[j,j+\text{len}-1])

则这个三元数对 ((i,j,\text{len})) 对 (S) 的神秘度的贡献是 (\text{len})。

输入一个字符串，输出其所有前缀的神秘度。由于这个值过大，所以请对 (10^9+7) 取模并输出。

输入格式

输入仅一行：仅由小写字母构成的字符串 (S)。

输出格式

输出共 (n) 行，第 (i) 行的整数是前 (i) 个位置表示的前缀的神秘度。

样例

样例 1 输入

aaaaaa

输出

0
0
2
7
19
40

样例 2 输入

ababab

输出

0
0
0
0
3
10

样例 3 输入

aabababacbacbac

输出

0
0
0
0
0
3
10
22
22
22
22
22
26
35
50

数据范围与提示

对于 20% 的数据，(1\leqslant n\leqslant 1000)； 对于 40% 的数据，(1\leqslant n\leqslant 5\times 10^5)，且 (S) 仅由 (\texttt{a}) 构成； 对于 60% 的数据，(1\leqslant n\leqslant 10^5)； 对于 100% 的数据，(1\leqslant n\leqslant 5\times 10^5)。