H2. Ранг матрицы (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями этой задачи в ограничениях на $$$k$$$. Вы можете использовать взломы только если сданы обе версии задачи.

Вам даны целые числа $$$n$$$, $$$p$$$ и $$$k$$$. Гарантируется, что $$$p$$$ является простым числом.

Для каждого $$$r$$$ от $$$0$$$ до $$$k$$$ найдите количество $$$n \times n$$$ матриц $$$A$$$ над полем$$$^\dagger$$$ целых чисел по модулю $$$p$$$, таких что ранг$$$^\ddagger$$$ матрицы $$$A$$$ в точности равен $$$r$$$. Поскольку эти значения могут быть большими, вам требуется вывести их по модулю $$$998\,244\,353$$$.

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

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

Входные данные

Первая строка ввода содержит три целых числа $$$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$$$ целое число, ответы для каждого $$$r$$$ от $$$0$$$ до $$$k$$$.

Примеры
Входные данные
3 2 3
Выходные данные
1 49 294 168 
Входные данные
1 51549919 2
Выходные данные
1 51549918 0