Good Bye 2023 |
---|
Finished |
This is the easy 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)
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 5000$$$).
It is guaranteed that $$$p$$$ is a prime number.
Output $$$k+1$$$ integers, the answers for each $$$r$$$ from $$$0$$$ to $$$k$$$.
3 2 3
1 49 294 168
1 51549919 2
1 51549918 0
Name |
---|