9488: ABC217 —— G - Groups
[Creator : ]
Description
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.
Input
Input is given from Standard Input in the following format:
```
$N$ $M$
```
```
$N$ $M$
```
Output
Print $N$ lines.
The $i$-th line should contain the answer for the problem with $k=i$.
The $i$-th line should contain the answer for the problem with $k=i$.
Constraints
- $2 \leq N \leq 5000$
- $2 \leq M \leq N$
- All values in input are integers.
- $2 \leq M \leq N$
- All values in input are integers.
Sample 1 Input
4 2
Sample 1 Output
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 2 Input
6 6
Sample 2 Output
1
31
90
65
15
1
You can divide them as you like.
Sample 3 Input
20 5
Sample 3 Output
0
0
0
331776
207028224
204931064
814022582
544352515
755619435
401403040
323173195
538468102
309259764
722947327
162115584
10228144
423360
10960
160
1