Counting Graph Configurations with Given Shortest Distances

You are given a labeled simple undirected connected graph with all edge weights equal to \(1\). The graph has \(n\) vertices and \(m\) edges. You are also given an array \(d\) of \(n\) integers, where \(d_i\) is the shortest distance from vertex \(1\) to vertex \(i\) in the graph. In particular, \(d_1=0\).

The graph must satisfy that for every vertex \(v\) with \(d_v>0\), there is at least one edge connecting \(v\) to some vertex \(u\) with \(d_u=d_v-1\). Note that an edge \((u,v)\) is allowed only if \(|d_u-d_v|\le 1\); otherwise, adding it would reduce the shortest distance for one of its endpoints. Two graphs are considered different if there exists an edge which is present in one graph but not in the other.

Determine the number of graphs that have exactly \(m\) edges and satisfy the given distance conditions. Since the answer can be large, output it modulo \(998244353\).

Input/Output format details: See below.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le \text{constraints})\), the number of vertices and edges, respectively. The second line contains \(n\) space‐separated integers \(d_1,d_2,\ldots,d_n\), where \(d_i\) is the shortest distance from vertex 1 to vertex \(i\). It is guaranteed that \(d_1=0\) and that there is at least one graph satisfying the conditions.

Note: The vertices are labeled from 1 to \(n\).

outputFormat

Output a single integer, the number of graphs with exactly \(m\) edges that satisfy the given shortest path distances, modulo \(998244353\).

sample

3 2
0 1 1

1