String God's String

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

One day, the String God showed Akura a very beautiful string $s$ that contains only the characters $a$ and $b$ . Akura was mesmerized and wanted to replicate the same string.

Akura starts with an empty string, and he can add either an $a$ or a $b$ to the end of the string each time until he gets $s$ . However, the String God’s string has very powerful antimemetics, and once Akura looks away from $s$ , he forgets all the information about it. Thus, Akura doesn’t know which character to add each step and can only rely on intuition. After adding a character, he can look at $s$ to check if he made a mistake. If he adds the wrong character, Akura will correct the mistake in the best possible way.

Specifically, let $f(x)$ be the suffix of Akura’s string of length $x$ , $g(x)$ be the prefix of $s$ of length $x$ , and $c$ be the largest $c$ such that $f(c)=g(c)$ :

If the character Akura adds increases $c$ by $1$ , he added the correct character.
Otherwise, he added the wrong character. He will then add the fewest number of characters to match $g(c)$ again, and then add the correct character to increase the match length to $c + 1$ .

Once $c$ equals the length of $s$ , Akura will have a suffix equal to $s$ , thus creating a copy of $s$ .

For example, if the String God’s string is $abba$ and Akura currently has $ab$ . If Akura adds an $a$ , which is incorrect, he will add a $b$ to match the prefix of length $2$ again, making the string $abab$ , and then add a $b$ to match the prefix of length $3$ .

Akura wants to know the number of possible ways to add $n$ characters to complete this task. He wants the answers for all $n \in [0, t]$ . Since the answer can be very large, you only need to provide the answer modulo $\textstyle 998,244,353$ .

输入描述:

The first line contains an integer  (), representing the upper limit of .

The second line contains a string  (the length of  does not exceed  and it contains only the characters  and ).

输出描述:

Output $t+1$ integers in one line, where the $i$ -th integer represents the number of ways to add $n = i-1$ characters to obtain $s$ , modulo $\textstyle 998,244,353$ .

示例1

输入

复制

5
abba

输出

复制

0 0 0 0 1 2