9855: ABC303 —— Ex - Constrained Tree Degree
[Creator : ]
Description
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$.
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$.
Input
The input is given from Standard Input in the following format:
```
$N$ $K$
$S_1$ $\ldots$ $S_K$
```
```
$N$ $K$
$S_1$ $\ldots$ $S_K$
```
Output
Print the number, modulo $998244353$, of the conforming trees $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.
- $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.
Sample 1 Input
4 2
1 3
Sample 1 Output
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 2 Input
10 5
1 2 3 5 6
Sample 2 Output
68521950
Sample 3 Input
100 5
1 2 3 14 15
Sample 3 Output
888770956