AT_utpc2022_e Parallel Swapping

長さ $ N $ の順列 $ P=(P_1,P_2,\ldots,P_N), Q=(Q_1,Q_2,\ldots,Q_N) $ があります。はじめ $ P_i = Q_i = i $ $ (1 \leq i \leq N) $ です。 この $ 2 $ つの順列に対して、以下の操作を $ 0 $ 回以上好きなだけ繰り返します。 - $ 1 \le i \le M $ を満たす整数 $ i $ を選ぶ。 $ P $ の $ a_i $ 番目と $ b_i $ 番目の要素を入れ替え、 $ Q $ の $ c_i $ 番目と $ d_i $ 番目の要素を入れ替える。 操作後の $ P, Q $ の状態の組としてありうるものの個数を $ 998244353 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ \vdots $ $ a_M $ $ b_M $ $ c_M $ $ d_M $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 ありうる $ P, Q $ の状態の組は $ P=(1, 2, 3), Q=(1, 2, 3) $ と $ P=(2, 1, 3), Q=(1, 3, 2) $ の $ 2 $ つです。 ### Constraints - 入力は全て整数 - $ 2 \leq N \leq 5000 $ - $ 0 \leq M \leq 5000 $ - $ 1 \le a_i, b_i, c_i, d_i \le N $ - $ a_i < b_i $ - $ c_i < d_i $ - $ i \neq j $ ならば $ (a_i, b_i, c_i, d_i) \neq (a_j, b_j, c_j, d_j) $