Contest Duration: - (local time) (100 minutes) Back to Home
G - Groups /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 問題：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 の問題の答えを出力せよ。

### 入力例 1

4 2


### 出力例 1

0
2
4
1


• 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 通りです。

### 入力例 2

6 6


### 出力例 2

1
31
90
65
15
1


### 入力例 3

20 5


### 出力例 3

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


Score : 600 points

### Problem Statement

You are given positive integers N and M. For each k=1,\ldots,N, solve the following problem.

• Problem: We will divide N people with ID numbers 1 through N into k non-empty groups. Here, people whose ID numbers are equal modulo M cannot belong to the same group.
How many such ways are there to divide people into groups?
Since the answer may be enormous, find it modulo 998244353.

Here, two ways to divide people into groups are considered different when there is a pair (x, y) such that Person x and Person y belong to the same group in one way but not in the other.

### Constraints

• 2 \leq N \leq 5000
• 2 \leq M \leq N
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M


### Output

Print N lines.

The i-th line should contain the answer for the problem with k=i.

### Sample Input 1

4 2


### Sample Output 1

0
2
4
1


People whose ID numbers are equal modulo 2 cannot belong to the same group. That is, Person 1 and Person 3 cannot belong to the same group, and neither can Person 2 and Person 4.

• There is no way to divide the four into one group.
• There are two ways to divide the four into two groups: \{\{1,2\},\{3,4\}\} and \{\{1,4\},\{2,3\}\}.
• There are four ways to divide the four into three groups: \{\{1,2\},\{3\},\{4\}\}, \{\{1,4\},\{2\},\{3\}\}, \{\{1\},\{2,3\},\{4\}\}, and \{\{1\},\{2\},\{3,4\}\}.
• There is one way to divide the four into four groups: \{\{1\},\{2\},\{3\},\{4\}\}.

### Sample Input 2

6 6


### Sample Output 2

1
31
90
65
15
1


You can divide them as you like.

### Sample Input 3

20 5


### Sample Output 3

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


Be sure to find the answer modulo 998244353.