Counting Ordered Rooted Trees with Depth Constraint

Given a fixed positive integer k, we define w_k(n) to be the number of ordered (i.e. the children of each node are ordered) and unlabelled rooted trees which satisfy the following condition:

• The tree has between 1 and n nodes.
• Every node at depth k is not a leaf (i.e. it has at least one child).

Note that the depth of a node is defined as the length of the unique simple path from the root to that node (the root has depth 0). When a tree does not have any node at depth k, it is considered valid.

Your task is: Given a fixed positive integer k and multiple queries each specifying a positive integer n, for each query compute w_k(n) modulo 998244353.

Mathematical Formulation:

Let w_k(n) be the number of ordered rooted trees with total nodes n' satisfying 1 ≤ n' ≤ n and such that every node at depth k has at least one child. Report the answer modulo 998244353.

inputFormat

The first line contains two integers k and q (1 ≤ k, q ≤ ...), where k is the fixed depth at which no leaf is allowed, and q is the number of queries.

Then q lines follow, each containing a positive integer n (1 ≤ n ≤ ...), representing a query.

outputFormat

For each query, output a single line containing the value of w_k(n) modulo 998244353.

sample

1 3
1
2
3

1
1
2