Matrix Rank (Easy Version) (Codeforces 1916H1)
Tags: Math, matrices

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


Sample Inputs:
3 2 3

1 51549919 2

Sample Outputs:
1 49 294 168

1 51549918 0

Solution (Python):
M = 998244353
P = pow
(n, p, k) = map(int, input().split())
a = [1]
m = P(p, n, M)
i = 1
R = 1
g = 1
for r in range(k):
    i = i * (m - R) % M
    R = R * p % M
    g = g * P(p, r, M) * (R - 1) % M
    a.append(i * i * P(g, -1, M) % M if g else 0)
print(' '.join(map(str, a)))

Solution (Python):
M = 998244353
P = pow
(n, p, k) = map(int, input().split())
a = [1]
m = P(p, n, M)
i = 1
R = 1
g = 1
for r in range(k):
    i = i * (m - R) % M
    R = R * p % M
    g = g * P(p, r, M) * (R - 1) % M
    a.append(i * i * P(g, -1, M) % M if g else 0)
print(' '.join(map(str, a)))

Solution (Python):
M = 998244353
P = pow
(n, p, k) = map(int, input().split())
a = [1]
m = P(p, n, M)
i = 1
R = 1
g = 1
for r in range(k):
    i = i * (m - R) % M
    R = R * p % M
    g = g * P(p, r, M) * (R - 1) % M
    a.append(i * i * P(g, -1, M) % M if g else 0)
print(' '.join(map(str, a)))