当前没有测试数据。

试题：有限制的树的度

得分：$600$ 分

问题描述

给定一个整数 $N$ 和一个集合 $S=\lbrace S_1,S_2,\ldots,S_K\rbrace$，其中的整数取值范围在 $1$ 到 $N-1$ 之间。

找出满足以下条件的树 $T$ 的数量，对 $998244353$ 取模：

• 对于所有 $i\ (1\leq i \leq N)$，都有 $d_i\in S$，其中 $d_i$ 是顶点 $i$ 在 $T$ 中的度。

约束条件

• $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

如果一个树满足条件，那么其中一个顶点的度为 $3$，其他顶点的度为 $1$。因此，答案是 $4$。

10 5
1 2 3 5 6

68521950

100 5
1 2 3 14 15

888770956

输出结果对 $998244353$ 取模。