Score : $600$ points

问题描述

给定一个整数 $N$ 和一个包含整数的集合 $S=\lbrace S_1,S_2,\ldots,S_K\rbrace$，其中所有元素均在 $1$ 到 $N-1$ 的范围内。

求满足以下条件的、具有 $N$ 个顶点（编号为 $1$ 至 $N$）的树 $T$ 的个数，对 $998244353$ 取模：

• 对于所有 $i\ (1\leq i \leq N)$，顶点 $i$ 在树 $T$ 中的度数 $d_i$ 都属于集合 $S$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given an integer $N$ and a set $S=\lbrace S_1,S_2,\ldots,S_K\rbrace$ consisting of integers between $1$ and $N-1$.

Find the number, modulo $998244353$, of trees $T$ with $N$ vertices numbered $1$ through $N$ such that:

• $d_i\in S$ for all $i\ (1\leq i \leq N)$, where $d_i$ is the degree of vertex $i$ in $T$.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$S_1$ $\ldots$ $S_K$

Output

Print the number, modulo $998244353$, of the conforming trees $T$.

Sample Input 1

4 2
1 3

Sample Output 1

4

A tree satisfies the condition if the degree of one vertex is $3$ and the others' are $1$. Thus, the answer is $4$.

Sample Input 2

10 5
1 2 3 5 6

Sample Output 2

68521950

Sample Input 3

100 5
1 2 3 14 15

Sample Output 3

888770956

Print the count modulo $998244353$.

update @ 2024/3/10 08:32:45