配点 : 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