問題文

長さ 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 で割ったあまりを求めてください。

制約

• 入力は全て整数
• 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)

入力例 1

3 1
1 2 2 3

出力例 1

2

ありうる P, Q の状態の組は P=(1, 2, 3), Q=(1, 2, 3) と P=(2, 1, 3), Q=(1, 3, 2) の 2 つです。

入力例 2

4 3
1 2 2 4
2 3 1 2
1 4 2 3

出力例 2

288

入力例 3

2 0

出力例 3

1