Good Permutations and Marking Process

Consider a permutation (a_1,a_2,\dots,a_n) of ({1,2,\dots,n}). For a given integer (m) (with (1\le m\le n)), we perform the following process on the permutation.

Initially, set an index (t=m) and define the previous marked number (p_0=0). Then, repeatedly do the following until the process stops:

• From the positions \(1\) to \(t\) (1-indexed), choose an element which has not been marked before and mark it. Let the number at that position be \(x\).
• If \(x>p_{\text{prev}}\) (with \(p_{\text{prev}}\) being the number chosen in the previous marking, and with \(p_0=0\) for the first marking) and \(t<n\), then increment \(t\) by \(1\); otherwise, the process stops.

We say that the permutation is good (with respect to (m)) if there exists some valid selection order (i.e. a choice at each step among the available, unmarked positions) such that after several operations the value of (t) becomes (n). Notice that the process may stop before all elements are marked; what matters is that at some point (t=n).

It can be proved that the process will succeed if and only if there exists a sequence of ((n-m)) positions (used in the operations) satisfying the following: if we denote these positions by (i_1,i_2,\dots,i_{n-m}) (each chosen from the available indices during the process), then the conditions

[ \begin{aligned} i_1 &\le m,\ i_2 &\le m+1,\ &,,\vdots \ i_{n-m} &\le m+n-m-1 = n-1, \end{aligned} ]

hold (here the indices are 1-indexed) and the corresponding values are in strictly increasing order, i.e.,

[ a_{i_1} < a_{i_2} < \cdots < a_{i_{n-m}}. ]

For example, when (n=3) and (m=1), the process is forced: one must mark the element at position 1 first, then the only option is to mark the element at position 2. Hence the permutation is good if and only if (a_1 < a_2). On the other hand, when (m=2) for (n=3) the process has a choice in the first step so that all permutations become good.

Your task is: given (n) and (q) queries, each query giving an integer (m), compute the ratio of good permutations among all (n!) permutations modulo (998244353). In other words, if there are (x) good permutations, output (x \cdot (n!)^{-1}) modulo (998244353).

Note: It is guaranteed that (1\le m\le n).

inputFormat

The first line contains two integers (n) and (q) (the length of the permutation and the number of queries). Each of the next (q) lines contains a single integer (m).

outputFormat

For each query, output a single integer: the value of (\frac{x}{n!}) modulo (998244353), where (x) is the number of good permutations for the given (m).

sample

3 2
1
2

499122177
1

</p>