Problem Description

How many undirected simple connected graphs with $n$ vertices and $m$ edges, without self-loops or multiple edges, exist such that removing the vertex with index $i$ results in the graph being split into $a_i$ connected components? Specifically, we guarantee that $n-1 \le m \le n+1$, and the answer is non-zero.

The answer should be taken modulo $998,244,353$.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers, where the $i$-th integer is $a_i$.

Output Format

Output a single integer, which is the result of the answer taken modulo $998,244,353$.

Sample Input and Output

Sample Input #1

4 4
2 1 1 1

Sample Output #1

3

Sample Input #2

4 5
1 1 1 1

Sample Output #2

6

Sample Input #3

5 6
1 1 2 1 1

Sample Output #3

27

Sample Input #4

6 6
1 2 3 1 1 1

Sample Output #4

30

Sample Input #5

6 5
2 1 1 1 1 4

Sample Output #5

4

Sample Input #6

8 7
1 1 3 1 2 2 2 2

Sample Output #6

360

Sample Input #7

8 8
1 1 1 1 2 2 2 2

Sample Output #7

2520

Sample Input #8

8 9
1 1 1 1 1 1 2 3

Sample Output #8

9240

Sample Input #9

10 11
1 1 1 4 2 2 2 1 1 1

Sample Output #9

105840

Sample Input #10

12 13
1 1 1 1 1 1 1 1 1 1 1 1

Sample Output #10

518269694

Notes

Sample 1 Explanation

There are three possible graphs, with the four edges connected as follows:

1. $(1,2),(1,3),(1,4),(2,3)$.
2. $(1,2),(1,3),(1,4),(2,4)$.
3. $(1,2),(1,3),(1,4),(3,4)$.

Data Range

For all data, it is guaranteed that $4 \le n \le 10^5$, $n-1 \le m \le n+1$, $1 \le a_i < n$, $n \le \sum_{i=1}^n a_i \le 2n-2$, and the answer is non-zero.

见题面 Input 部分

见题面 Output 部分