Problem Statement

You are given a positive integer $N$ and a sequence of $M$ non-negative integers $A = (A_{1}, A_{2}, \dots, A_{M})$.

Here, all elements of $A$ are distinct integers between $0$ and $N-1$, inclusive.

Find the number, modulo $998244353$, of permutations $P$ of $(0, 1, \dots, N-1)$ that satisfy the following condition.

• After initializing a sequence $B = (B_{1}, B_{2}, \dots, B_{N})$ to $P$, it is possible to make $B = A$ by repeating the following operation some number of times:
• Choose $l$ and $r$ such that $1 \leq l \leq r \leq |B|$, and if $\mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\})$ is contained in $B$, remove it from $B$.

What is $\mathrm{mex}(X)$? For a finite set $X$ of non-negative integers, $\mathrm{mex}(X)$ is defined as the smallest non-negative integer that is not in $X$.

Constraints

• $1 \leq M \leq N \leq 500$
• $0 \leq A_{i} < N$
• All elements of $A$ are distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_{1} A_{2} \cdots A_{M}

Output

Print the answer.