题目背景

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 优化。