/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 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 で割った余りを出力せよ。
入力例 1
4 2 1 3
出力例 1
4
ある 1 つの頂点の次数が 3 であり、ほかの頂点の次数が 1 であるような木が条件を満たします。よって答えは 4 個です。
入力例 2
10 5 1 2 3 5 6
出力例 2
68521950
入力例 3
100 5 1 2 3 14 15
出力例 3
888770956
個数を 998244353 で割った余りを出力してください。
Score : 600 points
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.