P8107 [Cnoi2021] Future Problem

In the duplicate-checking stage of Cnoi2021, Cirno found that in the distant future, a problem from the 2077 freshman contest of Earthworm Technology University (some unknown school from the outside world) unexpectedly had a $9\%$ similarity to a problem in this set. > Given a positive integer $n$, when generating a uniformly random permutation of length $n$, find the expected number of inversions in the permutation, and output the answer modulo $10^9+7$. (2077-xidian-freshman-online Problem.D) The answer is clearly $\frac{n(n-1)}{4}$. As an arithmetic genius, Cirno saw it at a glance. But there is no need to worry: colliding with a future problem does not count as a collision, so this problem appears before you.

You are given two positive integers $n,k$. For all $\forall i \in [0,k)$, when generating a uniformly random permutation of length $n$, compute the probability that the number of inversions in the permutation modulo $k$ has remainder $i$. Output the answers modulo $998244353$.

One line containing two integers $n,k$.

One line containing $k$ integers separated by spaces. The $i$-th integer represents the probability that the number of inversions in the permutation modulo $k$ has remainder $i-1$.

**Sample Explanation** |Number of inversions|Permutations| |-----|-----| |0|$(1,2,3,4)$| |1|$(1,2,4,3)(1,3,2,4)(2,1,3,4)$| |2|$(1,3,4,2)(1,4,2,3)(2,1,4,3)(2,3,1,4)(3,1,2,4)$| |3|$(1,4,3,2)(2,3,4,1)(2,4,1,3)(3,1,4,2)(3,2,1,4)(4,1,2,3)$| |4|$(2,4,3,1)(3,2,4,1)(3,4,1,2)(4,1,3,2)(4,2,1,3)$| |5|$(3,4,2,1)(4,2,3,1)(4,3,1,2)$| |6|$(4,3,2,1)$| **Constraints** For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^5$, $2\le k\le 1000$. Re-collected from XDUCPC 2021 Onsite Contest F. Translated by ChatGPT 5