310981: CF1916H1. 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)
InputThe 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.
OutputOutput $k+1$ integers, the answers for each $r$ from $0$ to $k$.
ExamplesInput3 2 3Output
1 49 294 168Input
1 51549919 2Output
1 51549918 0
Output
这是一个关于矩阵秩的问题的简单版本。在这个问题中，你需要计算给定大小的矩阵在模素数p的情况下，具有特定秩r的矩阵的数量。对于每个r从0到k，你需要找出所有n×n的矩阵A，其秩恰好为r的数量，并将结果模998,244,353输出。
输入数据格式：
输入包含三个整数n, p和k，其中n表示矩阵的大小，p是一个素数，k表示需要计算的最大秩。满足条件：1 ≤ n ≤ 10^18, 2 ≤ p < 998,244,353, 0 ≤ k ≤ 5000。
输出数据格式：
输出k+1个整数，分别对应于每个r从0到k的答案。
示例：
输入：
3 2 3
输出：
1 49 294 168
输入：
1 51549919 2
输出：
1 51549918 0
请注意，以上输出结果均已模998,244,353处理。题目大意： 这是一个关于矩阵秩的问题的简单版本。在这个问题中，你需要计算给定大小的矩阵在模素数p的情况下，具有特定秩r的矩阵的数量。对于每个r从0到k，你需要找出所有n×n的矩阵A，其秩恰好为r的数量，并将结果模998,244,353输出。 输入数据格式： 输入包含三个整数n, p和k，其中n表示矩阵的大小，p是一个素数，k表示需要计算的最大秩。满足条件：1 ≤ n ≤ 10^18, 2 ≤ p < 998,244,353, 0 ≤ k ≤ 5000。 输出数据格式： 输出k+1个整数，分别对应于每个r从0到k的答案。 示例： 输入： 3 2 3 输出： 1 49 294 168 输入： 1 51549919 2 输出： 1 51549918 0 请注意，以上输出结果均已模998,244,353处理。