计数欧拉环（Counting Eulerian Circuits）

问题描述

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

一个欧拉环（Eulerian circuit）是指一条闭合路径：

• 遍历每条边恰好一次；
• 起点与终点相同；
• 边序列 $(e_0, e_1, \dots, e_{M-1})$ 是边集的一个排列；
• 对 $0 \le i < M-1$，边 $e_i$ 的终点等于边 $e_{i+1}$ 的起点；
• 边 $e_{M-1}$ 的终点等于边 $e_0$ 的起点。

注意：两个欧拉环若可通过循环移位（cyclic shift）相互得到，则视为相同。即仅计数以边 $e_0 = 0$（即第一条边为编号 0 的边）的欧拉环数量。

求满足上述条件的欧拉环数量，模 $998244353$。

约束条件

• $1 \leq N \leq 500$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq u_i, v_i < N$

输入

$N\ M$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$

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

4

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

36

10 4
0 0
0 0
0 0
0 0

6

#4

3 2
0 1
1 2

0