Background

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.

Problem Description

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

Input Format

One line containing two integers $n,k$.

Output Format

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

4 5

166374059 166374059 457528662 748683265 457528662

Hint

Sample Explanation

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