AT_waipc_qual_f.Sorted Factors

给定正整数 $N, M, K$。

满足下述条件的长度为 $N$ 的非负整数数列 $a=(a_1,a_2,\ldots,a_N)$ 被称为优秀数列。

• $0 \leq a_1 \leq a_2 \leq \cdots \leq a_N \leq M$

对于优秀数列 $a$，我们定义如下多项式 $f_a(x)$：

• $f_a(x)=\left(\prod_{1 \leq i \leq K} (a_i+x)\right) \times \left(\prod_{K+1 \leq i \leq N} a_i\right)$

将所有优秀数列 $a$ 的 $f_a(x)$ 全部相加，记所得多项式为 $g(x)$。显然 $g(x)$ 是 $K$ 次多项式。对于每个 $i$（$0 \leq i \leq K$），请计算 $g(x)$ 的 $i$ 次项系数 $g_i$ 模 $998244353$ 的余数。

输入以如下格式从标准输入给出。

$N$ $M$ $K$

请依次输出 $g_0, g_1, \ldots, g_K$，用空格分隔，结果均取模 $998244353$。

样例解释 1

所有优秀数列 $a$ 及对应的 $f_a(x)$ 如下：

• $a=(0,0)$：$f_a(x)=x^2$
• $a=(0,1)$：$f_a(x)=x^2+x$
• $a=(0,2)$：$f_a(x)=x^2+2x$
• $a=(1,1)$：$f_a(x)=x^2+2x+1$
• $a=(1,2)$：$f_a(x)=x^2+3x+2$
• $a=(2,2)$：$f_a(x)=x^2+4x+4$

将这些 $f_a(x)$ 相加，得到 $g(x)=6x^2+12x+7$。

数据范围

• $1 \leq K \leq N \leq 250000$
• $1 \leq M \leq 250000$
• 所有输入均为整数。

由 ChatGPT 5 翻译