codeforces#P1916H1. Matrix Rank (Easy Version)

    ID: 34322 远端评测题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>brute forcecombinatoricsdpmathmatrices*2700

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