CF1916H2.Matrix Rank (Hard Version)

This is the hard version of the problem. The only differences between the two versions of this problem are the constraints on $k$. You can make hacks only if all versions of the problem are solved.

You are given integers $n$, $p$ and $k$. $p$ is guaranteed to be a prime number.

For each $r$ from $0$ to $k$, find the number of $n \times n$ matrices $A$ of the field$^\dagger$ of integers modulo $p$ such that the rank$^\ddagger$ of $A$ is exactly $r$. Since these values are big, you are only required to output them modulo $998\,244\,353$.

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

$^\ddagger$ https://en.wikipedia.org/wiki/Rank_(linear_algebra)

这是该问题的困难版本。两个版本的唯一区别在于对 $k$ 的约束条件。只有当该问题的所有版本均被解决后，才允许进行 hack。

给定整数 $n$、$p$ 和 $k$。其中 $p$ 保证为质数。

对每个从 $0$ 到 $k$ 的 $r$，求满足以下条件的 $n \times n$ 矩阵 $A$ 的个数：矩阵 $A$ 的元素取自模 $p$ 的整数域$^\dagger$，且 $A$ 的秩$^\ddagger$ 恰好为 $r$。由于答案可能很大，你只需输出结果对 $998\,244\,353$ 取模后的值。

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

$^\ddagger$ https://en.wikipedia.org/wiki/Rank_(linear_algebra)

The first line of input contains three integers $n$, $p$ and $k$ ($1 \leq n \leq 10^{18}$, $2 \leq p \lt 998\,244\,353$, $0 \leq k \leq 5 \cdot 10^5$).

It is guaranteed that $p$ is a prime number.

输入的第一行包含三个整数 $n$、$p$ 和 $k$（$1 \leq n \leq 10^{18}$，$2 \leq p \lt 998\,244\,353$，$0 \leq k \leq 5 \cdot 10^5$）。

保证 $p$ 是一个质数。

Output $k+1$ integers, the answers for each $r$ from $0$ to $k$.

输出 $k+1$ 个整数，分别对应 $r$ 从 $0$ 到 $k$ 的每个答案。