分组

题目描述

给定正整数 $N$ 和 $M$。对于每个 $k=1,\ldots,N$，解决下面的问题。

问题：把 ID 为 $1$ 到 $N$ 的 $N$ 个人分成 $k$ 个非空组。 这里，ID 对 $M$ 取模相等的人不能分在同一组。

这样的分组方式有多少种？

由于答案可能非常大，请对 $998244353$ 取模。

这里，当存在一对 $(x,y)$，使得人 $x$ 和人 $y$ 在一种分组方式中同组、在另一种中不同组时，认为这两种分组方式不同。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$

输出格式

输出 $N$ 行。

第 $i$ 行输出 $k=i$ 时问题的答案。

样例

4 2

0
2
4
1

ID 对 $2$ 取模相等的人不能分在同一组。也就是说，人 $1$ 和人 $3$ 不能同组，人 $2$ 和人 $4$ 也不能同组。

把这四个人分成一组是不可能的。

分成两组有 $2$ 种方式：$\{\{1,2\},\{3,4\}\}$ 和 $\{\{1,4\},\{2,3\}\}$。

分成三组有 $4$ 种方式：$\{\{1,2\},\{3\},\{4\}\}$、$\{\{1,4\},\{2\},\{3\}\}$、$\{\{1\},\{2,3\},\{4\}\}$ 和 $\{\{1\},\{2\},\{3,4\}\}$。

分成四组有 $1$ 种方式：$\{\{1\},\{2\},\{3\},\{4\}\}$。

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$ 取模。

数据范围

• $2 \le N \le 5000$
• $2 \le M \le N$
• 输入中的所有值均为整数。