← 返回题目列表

Codeforces · 1916/H1

H1. 矩阵排名(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。该问题的两个版本之间的唯一区别是 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

给定整数 $$$n$$$、$$$p$$$ 和 $$$k$$$。 $$$p$$$ 保证是素数。

对于从 $$$0$$$ 到 $$$k$$$ 的每个 $$$r$$$,求 $$$n \times n$$$ 矩阵 $$$A$$$ 的域 $$$^\dagger$$$ 的整数模 $$$p$$$ 的数量,使得 $$$A$$$ 的排名 $$$^\ddagger$$$ 恰好是$$$r$$$。由于这些值很大,因此您只需输出它们对 $$$998\,244\,353$$$ 取模即可。

$$$^\dagger$$$ https://en.wikipedia.org/wiki/Field_(数学)

$$$^\ddagger$$$ https://en.wikipedia.org/wiki/Rank_(线性代数)

输入

输入的第一行包含三个整数 $$$n$$$、$$$p$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$、$$$2 \leq p < 998\,244\,353$$$、$$$0 \leq k \leq 5000$$$)。

保证 $$$p$$$ 是素数。

输出

输出$$$k+1$$$整数,从$$$0$$$到$$$k$$$的每个$$$r$$$的答案。

示例

输入 #1

3 2 3

输出 #1

1 49 294 168

输入 #2

1 51549919 2

输出 #2

1 51549918 0