問題文

一列に並んだ $N$ 個の電球があり、マスには左から順番に $1,2,3,…N$ の番号がついています。 最初は全ての電球の明かりがついていません。

あなたは $M$ 種類の操作を好きな順に好きな回数だけ行って電球の明かりをつけたり消したりできます。$i$ 種類目の操作は以下の通りです。

• 連続する $x_i$ 個の電球を選び、明かりがついている電球の明かりを消し、ついていない電球の明かりをつける。

明かりのついている電球の集合としてありうるものは何通り得られますか。答えを $998244353$ で割ったあまりを出力してください。

制約

• $1 \leq N \leq 10^9$
• $1 \leq M \leq 2\times 10^5$
• $1 \leq x_i \leq N$ $(1 \leq i \leq M)$

入力

入力はすべて整数である。

N M
x_1 x_2 ... x_M

出力

明かりのついている電球の集合としてありうるものの場合の数を $998244353$ で割ったあまりを出力してください。

サンプル

4 1
3

4

明かりのついている電球の集合としてあり得るものは $\{\}, \{1,2,3\}, \{2,3,4\}, \{1,4\}$ の $4$ 通りがあり得ます。

100000 3
21 57 3

134565347