双六 5

题目描述

有一个棋盘游戏,共有 $N+1$ 个方格:方格 $0$、方格 $1$、$\dots$、方格 $N$。

你有一个骰子,掷出的整数在 $1$ 到 $K$ 之间,每个结果等概率出现。

你从方格 $0$ 出发,重复以下操作,直到到达方格 $N$:

掷骰子。设当前所在方格为 $x$,掷出的数为 $y$,则移动到方格 $\min(N, x+y)$。

设 $P_i$ 为恰好经过 $i$ 次操作到达方格 $N$ 的概率。请计算 $P_1, P_2, \dots, P_N$ 对 $998244353$ 取模后的值。

「对 $998244353$ 取模的概率」是什么意思? 可以证明,所求概率总是有理数。 在本问题的约束下,还可以证明,当把这些值表示成互质整数 $P$ 和 $Q$ 的比 $\frac{P}{Q}$ 时,恰好存在一个满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R \lt 998244353$ 的整数 $R$。请找出这个 $R$。

输入格式

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

$N$ $K$

输出格式

输出 $N$ 行。第 $i$ 行应输出 $P_i$ 对 $998244353$ 取模后的值。

样例

3 2

0
249561089
748683265

例如,在以下情况下,恰好经过两次操作到达方格 $N$:

第一次掷出 $1$,第二次掷出 $2$。

第一次掷出 $2$,第二次掷出 $1$。

第一次掷出 $2$,第二次掷出 $2$。

因此,$P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4}$。由于 $249561089 \times 4 \equiv 3 \pmod{998244353}$,所以 $P_2$ 输出 $249561089$。

5 5

598946612
479157290
463185380
682000542
771443236

10 6

0
166374059
207967574
610038216
177927813
630578223
902091444
412046453
481340945
404612686

数据范围

• $1 \le K \le N \le 2 \times 10^5$
• $N$ 和 $K$ 是整数。