310981: CF1916H1. Matrix Rank (Easy Version)

H1. Matrix Rank (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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)

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$.

ExamplesInput

3 2 3

Output

1 49 294 168 

Input

1 51549919 2

Output

1 51549918 0 

题目大意：
这是一个关于矩阵秩的问题的简单版本。在这个问题中，你需要计算给定大小的矩阵在模素数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处理。