Background

Look at the sky, I'm still here

I'll be alive next year

I can make something good, oh

Something good

Enhanced version of this problem: U148588.

Problem Description

Mivik once again treated $(x+y)^2$ as $(x^2+y^2)$ when calculating. As this newbie looked up at the sky and saw white clouds drifting apart and merging together, he suddenly got inspired and wrote down a definition of the $k$-th average of a sequence $S$:

$$avg_k(S)=\frac{\sum_{i=1}^{|S|}{S_i^k}}{\left(\sum_{i=1}^{|S|}S_i\right)^k}$$

Mivik recalled everything that happened in 2020. There were $n$ important events to him: for example, hosting his first contest, witnessing Porter Robinson becoming active in the music scene again after a year, meeting that person... Some of these events were related to each other, meaning they formed an undirected graph. Mivik wrote down the sizes of all maximal connected components of this undirected graph on a sheet of white paper, believing that this represents everything he went through in 2020. Whether happy or sad, Mivik now folds this sheet into a paper airplane and is ready to fly it. But before that, he wants to compute the $k$-th average of the numbers on the paper, and record it in his diary as a souvenir of 2020.

Unfortunately, Mivik’s memory is not very good: he only remembers that there were $n$ major events in total, but he cannot remember the relationships between them. So Mivik asks you to compute, over all possible cases, the sum of the $k$-th averages of the numbers on the paper. In fact, Mivik does not care what $k$ is; he only cares whether the final answer looks nice in his diary, so he asks you to compute this value for all $k\in [0,K]$, so that he can choose one.

Two cases are essentially different if and only if there exist two events that are unrelated in one case but related in the other.

Formal statement: Let the connected component multiset $f(G)$ of an undirected graph $G$ be a sequence (in any order) consisting of the sizes of all maximal connected components of $G$. For all $k\in [0,K]$, compute:

$$\sum_{G\in S(n)}\frac{\sum_{i=1}^{|f(G)|}{f(G)_i^k}}{\left(\sum_{i=1}^{|f(G)|}f(G)_i\right)^k}$$

Here, $S(n)$ is the set of all undirected graphs with $n$ vertices. Output the answer modulo $998244353$. If you do not know how to take a rational number modulo a prime, see Modding Rational Numbers.

Input Format

One line with two positive integers, representing $n$ and $K$, with the same meaning as in the statement.

Output Format

Output $K+1$ lines. The $i$-th line contains one integer, representing the answer when $k=i-1$.

2 0

3

3 2

13
8
6

10 0

83728116

Hint

Explanation of Samples

Sample 1: There are only two undirected graphs on two vertices: with an edge and without an edge. Then when $k=0$, the answer is $\frac{1^0+1^0}{(1+1)^0}+\frac{2^0}{(2)^0}=1+2=3$.

Sample 2: There are $8$ undirected graphs on three vertices:

When $k=0$, the answer is $\frac{1^0+1^0+1^0}{(1+1+1)^0}+3\times\frac{1^0+2^0}{(1+2)^0}+4\times\frac{3^0}{(3)^0}=3+3\times2+4\times1=13$;

When $k=1$, the answer is $\frac{1^1+1^1+1^1}{(1+1+1)^1}+3\times\frac{1^1+2^1}{(1+2)^1}+4\times\frac{3^1}{(3)^1}=1+3\times1+4\times1=8$;

When $k=2$, the answer is $\frac{1^2+1^2+1^2}{(1+1+1)^2}+3\times\frac{1^2+2^2}{(1+2)^2}+4\times\frac{3^2}{(3)^2}=\frac13+3\times\frac59+4\times1=6$.

Constraints

For all testdata, $1\le n\le 2\cdot10^5$, $0\le K\le 5000$.

Subtask 1 (5 pts): Guaranteed $n=1$.

Subtask 2 (10 pts): Guaranteed $n=2$.

Subtask 3 (25 pts): Guaranteed $K=0$.

Subtask 4 (25 pts): Guaranteed $0\le K\le 10$.

Subtask 5 (35 pts): No additional constraints.

Translated by ChatGPT 5