A16406. 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)](https://en.wikipedia.org/wiki/Field_(mathematics))

$^\ddagger$ [https://en.wikipedia.org/wiki/Rank\_(linear\_algebra)](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 < 998\,244\,353$ , $0 \leq k \leq 5 \cdot 10^5$ ).

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

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