受限的节点度数

题目描述

给定一个整数 $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)$,有 $d_i\in S$,其中 $d_i$ 是顶点 $i$ 在 $T$ 中的度数。

输入格式

输入按以下格式从标准输入给出:

N K
S_1 … S_K

输出格式

输出满足条件的树 $T$ 的数量,对 $998244353$ 取模。

样例

4 2
1 3

4

满足条件的一棵树要求一个顶点的度数为 $3$,其余顶点的度数均为 $1$。因此答案为 $4$。

10 5
1 2 3 5 6

68521950

100 5
1 2 3 14 15

888770956

数据范围

• $2\leq N \leq 2\times 10^5$
• $1\leq K \leq N-1$
• $1\leq S_1 \lt S_2 \lt \ldots \lt S_K \leq N-1$
• 输入中的所有值均为整数。