H1. Matrix Rank (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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.ExamplesInput
3 2 3Output
1 49 294 168 Input
1 51549919 2Output
1 51549918 0 
3 2 3
1 49 294 168 
['brute force', 'combinatorics', 'dp', 'math', 'matrices', '*2700']