Problem Description

Let $w_k(n)$ be the number of ordered rooted unlabeled trees whose children are ordered and that satisfy the following conditions:

• The number of nodes $n_0\in[1,n]$.
• All nodes with depth $k$ are not leaves.

Given a fixed positive integer $k$, and then given a positive integer $n$ multiple times, compute $w_k(n)\bmod 998244353$.

Here, the depth of a node is defined as the length of the unique simple path from it to the root. For example, the depth of the root is $0$.

Input Format

This problem has multiple queries.

The first line contains a positive integer $id$, indicating the Subtask ID.

The second line contains two positive integers $q,k$, where $q$ is the number of queries.

The next $q$ lines each contain one positive integer $n$, describing a query.

Output Format

Output $q$ lines. Each line should be $w_k(n)\bmod 998244353$ for the corresponding query.

0
5 2
1
2
3
4
5

1
2
3
5
10

0
5 200
1
10
100
1000
10000

1
6918
721868074
972431902
815282281

Hint

Sample Explanation

Explanation for Sample 1:

When $k=2$, all valid trees with exactly $5$ nodes are:

Constraints

This problem uses bundled testdata.

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{Score} & \textbf{Special Properties}\\\hline \textsf{1} & 5 & 5 \\\hline \textsf{2} & 10^2 & 20\\\hline \textsf{3} & 2\times10^5 & 35 & k=1\\\hline \textsf{4} & 2\times10^5 & 40\\\hline\hline \end{array}$$

For all testdata, $1\le n,q,k\le 2\times10^5$.

Translated by ChatGPT 5