Это сложная версия задачи. Единственное различие между двумя версиями этой задачи в ограничениях на $$$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)