009 - Moke's Walking (Hard)

問題

もけちゃんは今、数直線上の原点に立っている。
暇を持て余しているもけちゃんは次のようなことを $N$ 回繰り返すことにした。

1. コインを投げる。
2. コインが表なら正の方向に $1$ 移動し、裏なら負の方向に $1$ 移動する。

これだけではつまらないと考えたもけちゃんは、次のような $M$ 個の制約を設けた。

• $c_i$ $(1 \leq i \leq M)$ 回目の移動直後、原点に立ってはならない。

この制約下でもけちゃんが遊ぶとき、$N$ 回目の移動直後、原点に立っている移動の仕方は何通り考えられるか。
$998244353$ で割った余りを求めよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$c_1$
$c_2$
$\vdots$
$c_M$

出力

あり得る通り数を $998244353$ で割った余りを一行で出力せよ。出力の末尾に改行を入れること。

制約

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq M \leq \min(20, N - 1)$
• $1 \leq c_i \leq N - 1$
• $c_i \neq c_j \ (i \neq j)$

入出力例

入力例１

6 4
1
2
4
5

出力例１

4

表を o、裏を x とすると、
{o, o, x, o, x, x}、{o, o, o, x, x, x}、{x, x, o, x, o, o}、{x, x, x, o, o, o}
の $4$ 通りが考えられる。

---

入力例２

11 7
6
7
1
5
3
4
2

出力例２

0

あり得る通り数が $0$ 通りになることもある。

---

入力例３

314 15
89
269
12
154
54
199
146
262
274
210
219
238
18
53
268

出力例３

267111239

$998244353$ で割った余りを出力することに注意せよ。