这是问题的困难版本。该问题的两个版本之间的唯一区别是 $$$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 5 \cdot 10^5$$$)。
保证 $$$p$$$ 是素数。
输出
输出$$$k+1$$$整数,从$$$0$$$到$$$k$$$的每个$$$r$$$的答案。
示例
输入 #1
3 2 3
输出 #1
1 49 294 168
输入 #2
1 51549919 2
输出 #2
1 51549918 0