配点 : $1600$ 点

問題文

整数 $N$ と $M$ が与えられます． 以下の手順で生成されうる整数列 $a=(a_1,a_2,\cdots,a_N)$ の個数を $998244353$ で割った余りを求めてください．

• $N$ 頂点，$M$ 辺からなる連結な無向グラフ $G$ を用意する． ここで，$G$ は自己ループを含んではならないが，多重辺を含んでもよい．
• $G$ 上で DFS を行い，$i$ ($1 \leq i \leq N$) 番目に訪れた頂点の次数を $a_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$ の時，$a=(2,4,1,3)$ を生成することは可能です． そのためには，以下のようなグラフ $G$ を用意すればよいです．

ここで，頂点にかかれている数は，その頂点を DFS で何番目に訪れたかを表しています．（$1$ と書かれた頂点から DFS を開始しています．） また，オレンジ色の矢印は DFS での遷移を示しており，その横の数字は辺をたどる順番を表しています．

制約

• $2 \leq N \leq M \leq 10^6$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

出力

答えを出力せよ．

2 2

1

あり得るのは $a=(2,2)$ のみです． $G$ は多重辺を持ってもよいことに注意してください．

3 4

9

10 20

186225754

100000 1000000

191021899