配点 : $600$ 点

問題文

整数 $N$ 及び $1$ 以上 $N-1$ 以下の整数からなる集合 $S=\lbrace S_1,S_2,\ldots,S_K\rbrace$ が与えられます。

頂点に $1$ から $N$ の番号がついた $N$ 頂点の木 $T$ のうち、以下の条件を満たすものの個数を $998244353$ で割った余りを答えてください。

• 任意の $i\ (1\leq i \leq N)$ について、$T$ の頂点 $i$ の次数を $d_i$ としたとき、 $d_i\in S$

制約

• $2\leq N \leq 2\times 10^5$
• $1\leq K \leq N-1$
• $1\leq S_1 < S_2 < \ldots < S_K \leq N-1$
• 入力は全て整数

入力

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

$N$ $K$

$S_1$ $\ldots$ $S_K$

出力

条件を満たす木 $T$ の個数を $998244353$ で割った余りを出力せよ。

4 2
1 3

4

ある $1$ つの頂点の次数が $3$ であり、ほかの頂点の次数が $1$ であるような木が条件を満たします。よって答えは $4$ 個です。

10 5
1 2 3 5 6

68521950

100 5
1 2 3 14 15

888770956

個数を $998244353$ で割った余りを出力してください。