Description

You are given a labeled, simple, undirected, connected graph where all edge weights are $1$. It has $n$ vertices and $m$ edges. You are also given the shortest path distances from vertex $1$ to every vertex. Find how many different graphs (forms) satisfy these conditions.

In particular, we define the shortest distance from vertex $1$ to vertex $1$ as $0$.

Two graphs are considered different if and only if there exists at least one edge $(u,v)$ that appears in one graph but does not appear in the other.

Since little_sun is extremely strong, the testdata guarantees that there is at least one graph that satisfies the conditions.

Output the answer modulo $998244353$.

Input Format

The first line contains two positive integers $n,m$, where $n$ is the number of vertices and $m$ is the number of edges.

The second line contains $n$ non-negative integers $d_1,d_2,\cdots,d_n$, representing the shortest path distance from vertex $1$ to each vertex.

Output Format

Output one line with one integer, the answer.

4 3
0 1 1 2

2

5 5
0 1 1 2 2

12

8 12
0 2 2 2 2 1 1 1

128601

Hint

Sample Explanation

For the first sample, there are two forms: $\{(1,2),(1,3),(2,4)\}$ and $\{(1,2),(1,3),(3,4)\}$.

For the second sample, I came up with a wonderful explanation, but unfortunately this blank space is too small to write it down.

Constraints

This problem uses bundled tests.

• Subtask 1 (10 pts): $n\le 7$, $m\le 14$, time limit 1s.
• Subtask 2 (20 pts): $n\le 50$, $m\le 600$, time limit 1s.
• Subtask 3 (20 pts): $n\le 1000$, $m\le 5000$, time limit 1s.
• Subtask 4 (50 pts): no special constraints, time limit 3s.

For $100\%$ of the data: $n\le 10^5$, $m\le 2\times 10^5$. Let $t_i=\sum_j[d_j=i]$. It is also required that $\sum_{i}t_it_{i-1}\le 2\times 10^5$.

This problem forces O2 optimization to be enabled.

Translated by ChatGPT 5