I. Inverse Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an integer $$$N$$$ and an integer sequence $$$X$$$ of length $$$M$$$. Count, modulo $$$998244353$$$, the number of permutations $$$P = (P_1,P_2,\ldots,P_N)$$$ of $$$(1,2,\ldots,N)$$$ that satisfy the following condition:

  • The lexicographically smallest subsequence of $$$P$$$ of length $$$M$$$ coincides with $$$X$$$.
Input

The first line contains integers $$$N$$$ ($$$1 \leq N \leq 250000$$$) and $$$M$$$ ($$$1 \leq M \leq N$$$).

The second line contains integers $$$X_1,X_2,\ldots,X_M$$$ ($$$1 \leq X_i \leq N$$$, $$$X_i \neq X_j$$$ for all $$$i \neq j$$$).

Output

Print the answer.

Examples
Input
3 2
1 2
Output
3
Input
10 5
2 7 8 3 6
Output
0
Input
5 5
1 2 3 4 5
Output
1