I. String
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Aqua and Hiyori love strings.

Today, Aqua gets a pretty string $$$s$$$ of length $$$n$$$. To improve Aqua's intelligence, Hiyori sets a problem for Aqua.

A set $$$S$$$ is said to be a pretty set when its elements are substrings of $$$s$$$ and for every pair of different substrings $$$(A, B)$$$ in $$$S$$$, $$$A$$$ is not the suffix of $$$B$$$ and $$$B$$$ is not the suffix of $$$A$$$.

Now, for each $$$k=1,2,\cdots,n$$$, Aqua should answer the number of pretty set $$$S$$$ which satisfies $$$|S|=k$$$. But she is stupid, could you help her?

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning.

Input

The only line contains a string $$$s\ (1\leq |s| \leq 10^5)$$$, consists of only lowercase letters.

Output

Print $$$n$$$ lines. The $$$i$$$-th line should contain the answer for $$$k=i$$$ modulo $$$998244353$$$.

Examples
Input
abb
Output
5
6
2
Input
aabdeffdg
Output
42
741
7151
41208
145149
305478
351810
170100
0
Note

In the first example:

  • When $$$k=1$$$, $$$S=\lbrace \mathrm{a}\rbrace,\lbrace \mathrm{b}\rbrace,\lbrace \mathrm{ab}\rbrace,\lbrace \mathrm{bb}\rbrace,\lbrace \mathrm{abb}\rbrace$$$.
  • When $$$k=2$$$, $$$S=\lbrace \mathrm{a},\mathrm{b}\rbrace,\lbrace \mathrm{a},\mathrm{ab}\rbrace,\lbrace \mathrm{a},\mathrm{abb}\rbrace,\lbrace \mathrm{a},\mathrm{bb}\rbrace,\lbrace \mathrm{ab},\mathrm{bb}\rbrace,\lbrace \mathrm{ab},\mathrm{abb}\rbrace$$$.
  • When $$$k=3$$$, $$$S=\lbrace \mathrm{a},\mathrm{ab},\mathrm{abb}\rbrace,\lbrace \mathrm{a},\mathrm{ab},\mathrm{bb}\rbrace$$$.