H2. Matrix Rank (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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)

Input

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

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

Examples
Input
3 2 3
Output
1 49 294 168
Input
1 51549919 2
Output
1 51549918 0