欧拉回路计数

【题目描述】

给定一个有向图 $G$，它由 $N$ 个顶点和 $M$ 条边组成。第 $i$ 条边从 $u_i$ 指向 $v_i$。

$G$ 的欧拉回路是由顶点序列 $(v_0,\ldots,v_{M-1})$ 与边序列 $(e_0,\ldots,e_{M-1})$ 组成的二元组，满足以下条件：

• $(e_0,\ldots,e_{M-1})$ 是 $(0, \ldots, M-1)$ 的一个排列。
• 对于 $0\leq i < M-1$，边 $e_i$ 从 $v_i$ 指向 $v_{i+1}$。边 $e_{M-1}$ 从 $v_{M-1}$ 指向 $v_0$。

注意，欧拉回路经过任意循环移位后仍然是欧拉回路。

求 $G$ 的欧拉回路数量，其中可以通过循环移位互相得到的欧拉回路视为相同（换言之，求满足 $e_0 = 0$ 的欧拉回路数量），并将结果对 $998244353$ 取模。

【输入】

$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$

【输出】

输出答案对 $998244353$ 取模的结果。

【输入样例】

3 6
0 1
0 1
1 2
1 2
2 0
2 0

【输出样例】

4

【输入样例2】

4 10
0 1
0 2
1 0
1 3
1 3
2 1
2 3
3 0
3 1
3 2

【输出样例2】

36

【输入样例3】

10 4
0 0
0 0
0 0
0 0

【输出样例3】

6

【输入样例4】

3 2
0 1
1 2

【输出样例4】

0

【数据范围】

• $1 \leq N \leq 500$
• $1 \leq M \leq 200000$
• $0 \leq u_i, v_i \lt N$

【来源】

Library Checker（yosupo06） counting_eulerian_circuits