Background

A polynomial problem for Ysuperman’s template testing.

[Data removed]

Problem Description

How many undirected simple connected graphs with $n$ vertices and $m$ edges are there, with no self-loops and no multiple edges, such that after deleting the vertex numbered $i$, the undirected graph is split into $a_i$ connected components. In particular, we guarantee $n-1 \le m \le n+1$, and the answer is not $0$.

Output the answer modulo $998,244,353$.

Input Format

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

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

Output Format

Output one integer per line, representing the result of the answer modulo $998,244,353$.

4 4
2 1 1 1

3

4 5
1 1 1 1

6

5 6
1 1 2 1 1

27

6 6
1 2 3 1 1 1

30

6 5
2 1 1 1 1 4

4

8 7
1 1 3 1 2 2 2 2

360

8 8
1 1 1 1 2 2 2 2

2520

8 9
1 1 1 1 1 1 2 3

9240

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

105840

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

518269694

Hint

Explanation for Sample 1

There are three possible graphs. The four edges in each case are:

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)$.

Constraints

For all testdata, it holds 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 guaranteed to be non-zero.

Translated by ChatGPT 5