You are given a directed graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge is directed from $u_ i$ to $v_ i$.

An eulerian circuit of $G$ is a pair of sequence of vertices $(v_ 0,\ldots,v_ {M-1})$ and sequence of edges $(e_ 0,\ldots,e_ {M-1})$ satisfying following conditions.

• $(e_ 0,\ldots,e_ {M-1})$ is a permutation of $(0, \ldots, M-1)$.
• For $0\leq i < M-1$, the edge $e_ i$ is directed from $v_ i$ to $v_ {i+1}$. The edge $e_ {M-1}$ is directed from $v_ {M-1}$ to $v_ 0$.

Note that an Eulerian circuit remains an Eulerian circuit after any cyclic shift.

Find the number of Eulerian circuits of $G$, considered the same if they can be obtained from one another by a cyclic shift (in other words, the number of Eulerian circuits with $e_ 0 = 0$), and give the result modulo $998244353$.