题目描述

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

input

aaaaaa

output

0
0
2
7
19
40

样例 2

input

ababab

output

0
0
0
0
3
10

样例 3

input

aabababacbacbac

output

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$。