問題文

N 個の文字あるいは文字列 X_1, X_2, \dots, X_N をこの順に連結させた文字列を X_1 + X_2 + \cdots + X_N と表記します。
また、文字列 X の i 文字目から j 文字目までを取り出した連続部分文字列を X[i,j] と表記します。
文字列に対して、バーガー、全バーガー、半バーガーを以下のように定義します。この定義はD問題と同じです。

• バーガーとは、全バーガーである文字列、および半バーガーである文字列
• 全バーガーとは、あるバーガー A とある文字 c に対して、c + A + c と書ける文字列、および空文字列
• 半バーガーとは、ある空でないバーガー A、B に対して、A + B と書ける文字列のうち、全バーガーでない文字列

例えば、abba や abbcca は全バーガー、aabb や abbacc は半バーガーですが、abbcbbc や ababa はバーガーではありません。

英小文字からなる文字列 S と 正の整数 K が与えられます。k = 0, 1, 2, \dots, K について、以下の問に答えてください。

• S[i, j] + T が全バーガーとなる、英小文字からなる文字列 T として考えられる長さの最小値が k となる (i, j) (1 \leq i \leq j \leq |S|) の個数を 998244353 で割った余りを求めよ。

制約

• 1 \leq |S| \leq 200{,}000
• 1 \leq K \leq 200{,}000
• S は英小文字からなる文字列
• K は整数

小課題

1. ( 1 点) K \leq 300

2. ( 99 点) 追加の制約はない

入力例 1

abcc
3

出力例 1

1
5
3
1

S[i,j] + T が全バーガーとなる T について、T の長さの最小値が k (0 \leq k \leq 3) となる (i, j) の組はそれぞれ以下になります。

• k = 0 のとき、(3, 4)
• k = 1 のとき、(1, 1), (2, 2), (3, 3), (4, 4), (2, 4)
• k = 2 のとき、(1, 2), (2, 3), (1, 4)
• k = 3 のとき、(1, 3)

S[1, 4] = abcc は、T = ba とすると全バーガーになります。T の長さが 1 以下のときは全バーガーにはなりません。

このテストケースは小課題 1 の制約を満たします。

入力例 2

fortississimo
7

出力例 2

4
19
20
21
15
8
3
1

このテストケースは小課題 1 の制約を満たします。