[ABC303Ex] Constrained Tree Degree
题意翻译
给定一个长度为 $K$ 的正整数序列 $S$，求有多少个不同的树 $T$ 使得：
* $T$ 中有 $N$ 个节点。
* 对于 $T$ 中的任意一个节点 $i$ 的度数 $d_i$，有 $d_i\in S$。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc303/tasks/abc303_h
整数 $ 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 $
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ K $ $ S_1 $ $ \ldots $ $ S_K $
输出格式
条件を満たす木 $ T $ の個数を $ 998244353 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
4 2
1 3输出样例 #1
4输入样例 #2
10 5
1 2 3 5 6输出样例 #2
68521950输入样例 #3
100 5
1 2 3 14 15输出样例 #3
888770956说明
### 制約
- $ 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 $
- 入力は全て整数
### Sample Explanation 1
ある $ 1 $ つの頂点の次数が $ 3 $ であり、ほかの頂点の次数が $ 1 $ であるような木が条件を満たします。よって答えは $ 4 $ 個です。
### Sample Explanation 3
個数を $ 998244353 $ で割った余りを出力してください。