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)](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 $ .