Counting Graphs with Specific Vertex‐Deletion Connectivity

You are given a simple undirected connected graph with n vertices and m edges (with no self‐loops or multiple edges) where m is either n−1, n, or n+1. For each vertex i (1 ≤ i ≤ n), when vertex i (together with all incident edges) is removed from the graph, the remaining graph splits into exactly a_i connected components. It is guaranteed that the answer is nonzero and that n−1 ≤ m ≤ n+1.

Your task is to compute the number of graphs satisfying these conditions. Since the answer can be very large, output it modulo \(998\,244\,353\).

Notes:

• If m = n−1, the graph is a tree and note that in any tree the number a_i equals the degree of vertex i.
• If m = n or m = n+1, the graph contains exactly one or two cycles respectively. In these cases the relation between the degree of a vertex and the connected components of the graph after deleting that vertex becomes more subtle.

Input Format: The first line contains two integers n and m. The second line contains n integers a₁, a₂, ..., a_n.

It is guaranteed that n−1 ≤ m ≤ n+1 and that there is at least one graph meeting the condition.

inputFormat

The input consists of two lines:

1. The first line contains two space‐separated integers n and m (the number of vertices and edges respectively).
2. The second line contains n space‐separated integers a₁, a₂, ..., a_n where a_i represents the number of connected components after deleting vertex i.

outputFormat

Output a single integer — the number of graphs satisfying the conditions modulo \(998\,244\,353\).

sample

3 2
1 2 1

1

</p>