102176: [AtCoder]ABC217 G - Groups

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$.

问题描述

给你两个正整数N和M。对于每个k=1,……,N，解决以下问题。

• 问题：我们要将ID号为1到N的N个人分成k个非空组。其中，ID号除以M余数相等的人不能属于同一个组。
  有几种将人分成组的方法？
  由于答案可能非常大，请对998244353取模。

这里，将人分成组的两种方式被认为是不同的，当存在一对(x, y)使得在一种方式中，Person x和Person y属于同一个组，而在另一种方式中却不属于同一个组。

约束

• 2 ≤ N ≤ 5000
• 2 ≤ M ≤ N
• 输入中的所有值都是整数。

输入

输入以标准输入的以下格式给出：

$N$ $M$

输出

打印N行。

第i行应包含k=i时问题的答案。

样例输入1

4 2

样例输出1

0
2
4
1

ID号除以2余数相等的人不能属于同一个组。也就是说，Person 1和Person 3不能属于同一个组，Person 2和Person 4也不能属于同一个组。

• 没有将四个人分成一个组的方法。
• 有两种将四个人分成两个组的方法：$\{\{1,2\},\{3,4\}\}$和$\{\{1,4\},\{2,3\}\}$。
• 有四种将四个人分成三个组的方法：$\{\{1,2\},\{3\},\{4\}\}$，$\{\{1,4\},\{2\},\{3\}\}$，$\{\{1\},\{2,3\},\{4\}\}$，和$\{\{1\},\{2\},\{3,4\}\}$。
• 有一种将四个人分成四个组的方法：$\{\{1\},\{2\},\{3\},\{4\}\}$。

样例输入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

请确保对998244353取模。