Background

“I can no longer recognize your eyes, and I am no longer thinking of your face;

you still did not say goodbye, and you turned into the night and left.”

Hilde Watching the Tide suddenly feels that this ever-rising tide is like continuously increasing passion: it keeps the time of a hot romance going, and excitement brings us even more passion. But the passion at the first meeting will eventually fade, and how many people can find an unchanging rhythm inside a cooling heartbeat and walk through this whole life?

Problem Description

Hilde wants to explore the question above, so she wants to do some statistics first, and she abstracts the problem.

For a permutation of length $n$, we maintain an index $t$, with initial value $t=m$.

Repeat the following process:

• Choose an unmarked element among those with indices in $1\sim t$, and mark it. If the marked number is larger than the previously marked number and $t<n$, then increase $t$ by $1$; otherwise, end the process. Before the first marking, the previously marked number is considered to be $0$.

We call such a permutation good:

• There exists some strategy such that after several operations, $t=n$.

Now, given $m$, find the proportion of good permutations of length $n$ among all permutations of length $n$, modulo $998244353$. In other words, if there are $x$ good permutations of length $n$, you need to output $\frac x{n!}$ modulo $998244353$. If you do not understand how to take a rational number modulo, you can read this problem.

There are $q$ queries, and each query gives an $m$.

Input Format

The first line contains two positive integers $n,q$.

The second line contains $q$ positive integers, representing $m_i$ for each query. It is guaranteed that the queries are in increasing order and pairwise distinct.

Output Format

For each query, output one integer per line, the answer modulo $998244353$.

5 3
1 2 3

291154603
249561089
1

50 5
4 7 9 14 17

344293672
864377042
192544332
688054502
97923957

Hint

Sample Explanation #1

The numbers of permutations that can make $t=n$ are $5,90,120$ respectively. There are $5!=120$ permutations in total, so you need to output $\frac{5}{120},\frac{90}{120},\frac{120}{120}$ respectively. After taking modulo, they become the sample output.

When $m=1$, the following are all permutations that can make $t=n$:

$$\{1,2,3,4,5\},\{2,3,4,5,1\},\{1,3,4,5,2\},\{1,2,4,5,3\},\{1,2,3,5,4\}$$

When $m=2$, here are some permutations that can make $t=n$:

$$\{1,4,2,3,5\},\{1,5,4,3,2\}$$

And some permutations that cannot make $t=n$:

$$\{5,4,3,2,1\},\{3,5,2,1,4\}$$

---

Constraints

It is guaranteed that $1\le q\le n\le 10^5$, $1\leq m_i \leq n$, and the queries $m_i$ are pairwise distinct and sorted in increasing order.

$$\def\arraystretch{1.5} \begin{array}{c|c|c|c}\hline \textbf{Subtask ID}&\bm{~~~~~~~n\le~~~~~~~}&\textbf{~~~Special Constraints~~~}&\textbf{~~Score~~}\cr\hline \textsf1 & 5 &&7\cr\hline \textsf2 & 200&&23\cr\hline \textsf3 & 2\times 10^4 &m_i=1& 9\cr \hline \textsf4 & 2\times 10^4 &2m_i\ge n& 3\cr \hline \textsf5 & 2\times 10^4 &&12\cr\hline \textsf6 & &q=1&36\cr\hline \textsf7 & &&10\cr\hline \end{array}$$

Hint: An $O(n^2)$ solution can pass quite a few points.

Translated by ChatGPT 5