题目描述

给定整数$N$和$M$。找出满足以下条件的整数序列$a=(a_1,a_2,\cdots,a_N)$的数量，模$998244353$。

• 提供一个有$N$个顶点和$M$条边的无向连通图$G$。其中，$G$可能不包含自环，但可能包含重边。
• 在$G$上执行DFS，并将$a_i$定义为第$i$个被访问的顶点的度数。更确切地说，执行下面的伪代码以获得$a$。

a = empty array

dfs(v):
    visited[v]=True
    a.append(degree[v])
    for u in g[v]:
        if not visited[u]:
            dfs(u)

dfs(arbitrary root)

这里，变量$g$以邻接表的形式表示图$G$，其中$g[v]$是按任意顺序排列的与顶点$v$相邻的顶点列表。

例如，当$N=4,M=5$时，可以通过提供以下图$G$生成$a=(2,4,1,3)$。

这里，顶点上的数字表示它们在DFS中被访问的顺序。（DFS从标记为$1$的顶点开始。）橙色箭头显示了DFS中的转换，旁边的数字表示遍历边的顺序。

约束条件

• $2 \leq N \leq M \leq 10^6$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$

输出

打印答案。

示例输入1

2 2

示例输出1

1

唯一可能的结果是$a=(2,2)$。注意$G$可能有重边。

示例输入2

3 4

示例输出2

9

示例输入3

10 20

示例输出3

186225754

示例输入4

100000 1000000

示例输出4

191021899