008 - Moke's Walking (Easy)

時間制限 2 秒 / メモリ制限 128 MB / 得点 100 / x 5 /


TLE
2sec
MLE
128MB
得点
100

問題

もけちゃんは今、数直線上の原点に立っている。
暇を持て余しているもけちゃんは次のようなことを $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 3 \times 10^3$
  • $1 \leq M \leq N - 1$
  • $1 \leq c_i \leq N - 1$
  • $c_i \neq c_j \ (i \neq j)$

入出力例

入力例1

6 4
1
2
4
5

出力例1

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$ 通りが考えられる。


入力例2

11 7
6
7
1
5
3
4
2

出力例2

0

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


入力例3

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

出力例3

267111239

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