配点 : $600$ 点

問題文

正の整数 $N,M$ が与えられます。$k=1,\ldots,N$ のそれぞれについて、次の問題を解いてください。

• 問題：$1$ から $N$ の番号がついた $N$ 人を、空でない $k$ 個のグループに分けます。 ただし、番号を $M$ で割ったあまりが等しい人は同じグループになることができません。 そのようなグループ分けの方法は何通りありますか？ 答えは非常に大きくなる可能性があるので $998244353$ で割ったあまりを求めてください。

ここで、グループ分けが異なるとは、一方では人 $x,y$ が同じグループであり、他方では異なるグループであるような $(x,y)$ が存在することを指すものとします。

制約

• $2 \leq N \leq 5000$
• $2 \leq M \leq N$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

出力

$N$ 行出力せよ。

$i$ 行目には $k=i$ の問題の答えを出力せよ。

4 2

0
2
4
1

番号を $2$ で割ったあまりが等しい人、すなわち、人 $1$ と $3$、人 $2$ と $4$ を同じグループにすることはできません。

• $1$ 個のグループにすることはできません。
• $2$ 個のグループにする方法は $\{\{1,2\},\{3,4\}\},\{\{1,4\},\{2,3\}\}$ の $2$ 通りです。
• $3$ 個のグループにする方法は $\{\{1,2\},\{3\},\{4\}\},\{\{1,4\},\{2\},\{3\}\},\{\{1\},\{2,3\},\{4\}\},\{\{1\},\{2\},\{3,4\}\}$ の $4$ 通りです。
• $4$ 個のグループにする方法は $\{\{1\},\{2\},\{3\},\{4\}\}$ の $1$ 通りです。

6 6

1
31
90
65
15
1

自由にグループ分けすることができます。

20 5

0
0
0
331776
207028224
204931064
814022582
544352515
755619435
401403040
323173195
538468102
309259764
722947327
162115584
10228144
423360
10960
160
1

答えを $998244353$ で割ったあまりを求めてください。