17253 | 오일러 회로 세기

$N$ 개의 정점과 $M$ 개의 간선으로 이루어진 유향 그래프 $G$ 가 주어진다. $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}$

문제에서 요구한 값 또는 값들을 출력한다.

오일러 회로 세기