题目描述

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 $t$ ($1 \leq t \leq 10^5$), representing the upper limit of $n$. The second line contains a string $s$ (the length of $s$ does not exceed $10^5$ and it contains only the characters $a$ and $b$).官方中文

输出格式

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$.官方中文