#P1916H1. Matrix Rank (Easy Version)
Matrix Rank (Easy Version)
Description
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$.
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 5000$).
It is guaranteed that $p$ is a prime number.
Output
Output $k+1$ integers, the answers for each $r$ from $0$ to $k$.
3 2 3
1 51549919 2
1 49 294 168
1 51549918 0