"I can no longer recognize your eyes, nor am I missing your face;

You left as the night without saying goodbye."

Hölder watches the tide and suddenly feels that this rising tide is like a continuously increasing passion. It sustains the duration of a passionate love, and the excitement brings us even more passion. However, the passion of first acquaintance will eventually fade. How many people can find the unchanging rhythm within the cooling heartbeat and walk through this life to the end?

Description

Hölder wants to investigate the question above. She wants to perform some statistics, so she abstracted the problem.

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

Repeat the following process:

• Choose an unmarked element from the indices $1 \sim t$ and mark it. If the marked number is greater than the previously marked number and $t < n$, then $t$ increments by $1$; otherwise, terminate this process. Before your first marking, the previously marked number is considered $0$.

We call such a permutation "good" if:

• There exists a method 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 the result of $\frac{x}{n!} \pmod{998244353}$.

There are $q$ queries, each providing an $m$.

Input

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

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

Output

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

Examples

Input 1

5 3
1 2 3

Output 1

291154603
249561089
1

Note 1

The number of permutations that can reach $t=n$ are $5, 90, 120$ respectively. There are $5! = 120$ permutations in total, so we need to output $\frac{5}{120}, \frac{90}{120}, \frac{120}{120}$ respectively. After taking the modulo, these are the answers in the sample output.

When $m=1$, the following are all permutations that can reach $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$, some permutations that can reach $t=n$ are:

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

And some that cannot reach $t=n$ are:

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

Input 2

50 5
4 7 9 14 17

Output 2

344293672
864377042
192544332
688054502
97923957

Subtasks

It is guaranteed that $1 \le q \le n \le 10^5$, $1 \le m_i \le n$, and the queried $m_i$ are distinct and sorted in ascending order.

Tip: $O(n^2)$ can pass quite a few test cases.