← 返回题目列表

AtCoder · utpc2022_e

E. 并行交换

中文机器翻译题面 查看原题

配点 : 100 点

問題文

长度 小于或等于 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 th 和 由于您拿了第 b_i 交换第……个元素,Q 可以得到第 c_i th 和 由于您拿了第 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)

入力

输入是按以下格式从标准输入给出的。

N M
a_1 b_1 c_1 d_1
\vdots
a_M b_M c_M d_M

出力

答案 请打印除以 1 行输出。


入力例 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