[QkOI#R1] Quark and Graph

SPFA 被卡时在做什么？有没有空？可以来计数吗？

现有一张边权全为 $1$ 的有标号简单无向连通图，其包含 $n$ 个节点和 $m$ 条边，已知该图上点 $1$ 到所有点的最短路长，求这张图有多少种形态。 特别地，我们认为点 $1$ 到点 $1$ 的最短路为 $0$。 两个图的形态不同当且仅当存在至少一条边 $(u,v)$ 在一张图中出现且在另一张图中没出现。 **由于 little_sun 太巨了，所以数据保证至少存在一张满足条件的图。** 答案对 $998244353$ 取模。

第一行两个正整数 $n,m$ —— $n$ 表示图的节点数，$m$ 表示图的边数。 第二行 $n$ 个非负整数 $d_1,d_2,\cdots,d_n$ 表示点 $1$ 到其它点的最短路。

输出一行一个整数表示你的答案。

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

### 样例解释 对于第一个样例，有 $\{(1,2),(1,3),(2,4)\}$ 和 $\{(1,2),(1,3),(3,4)\}$ 两种形态。 对于第二个样例，我想到了一个绝妙的解释，可惜这里空白太小，写不下。 ### 数据范围 **本题采用捆绑测试。** - Subtask 1（10 pts），满足 $n\le 7$，$m\le 14$，时限 1s； - Subtask 2（20 pts），满足 $n\le 50$，$m\le 600$，时限 1s； - Subtask 3（20 pts），满足 $n\le 1000$，$m\le 5000$，时限 1s； - Subtask 4（50 pts），无特殊限制，时限 3s。 对于 $100\%$ 的数据，满足 $n\le 10^5$，$m\le 2\times 10^5$。设 $t_i=\sum_j[d_j=i]$，还应满足 $\sum_{i}t_it_{i-1}\le 2\times 10^5$。 **本题强制开启 O2 优化。**