問題文

正整数 $N$ と長さ $M$ の正整数列 $A=(A_{1},A_{2},\dots, A_{M})$ が与えられます。

ここで、 $A$ の全ての要素は $1$ 以上 $N$ 以下の整数で、相異なります。

$(1, 2, \dots, N)$ の順列 $P = (P_{1}, P_{2}, \dots, P_{N})$ に対し、以下の条件を満たすような $1$ 以上 $M$ 以下の整数 $i$ の数を $P$ のスコアとします。

• $P$ の連続部分列であって、$(1, 2, \dots, A_{i})$ の順列であるものが存在する。

$(1, 2, \dots, N)$ の順列 $P$ であってスコアが偶数であるものの場合の数を $998244353$ で割ったあまりを求めてください。

制約

• $1\leq M\leq N\leq 2\times 10^{5}$
• $1\leq A_{i}\leq N$
• $A$ の要素は互いに相異なる
• 入力は全て整数

入力

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

出力

答えを出力してください。

サンプル

4 1
2

12

5 3
4 3 2

68

92 4
16 7 1 67

622918974

16 7
16 7 9 2 4 6 8

522888621