P8555 Hush Moon

“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](https://baike.baidu.com/item/%E4%B8%A5%E7%95%AF/23345630?fr=aladdin) 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?

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

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.

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

**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