考虑所有满足 $1 \le a < b \le n$ 的数对 $(a, b)$ 构成的集合。如果一个这些数对的排列满足以下条件，则称其为平衡的：对于任何满足 $1 \le a < b < c \le n$ 的 $a, b, c$，数对 $(a, c)$ 在排列中位于数对 $(a, b)$ 和 $(b, c)$ 之间。也就是说，这三个数对在排列中的出现顺序要么是 $(a, b), (a, c), (b, c)$，要么是 $(b, c), (a, c), (a, b)$。

此外，该排列还有 $m$ 个附加限制，其中第 $i$ 个限制规定数对 $(a_i, b_i)$ 必须在数对 $(c_i, d_i)$ 之前出现。计算满足这 $m$ 个限制的平衡排列的数量。

输入格式

输入的第一行包含两个空格分隔的整数 $n$ 和 $m$ ($2 \le n \le 10; 0 \le m \le 10$)。接下来的 $m$ 行中，第 $i$ 行包含四个空格分隔的整数 $a_i, b_i, c_i$ 和 $d_i$ ($1 \le a_i < b_i \le n; 1 \le c_i < d_i \le n$; 数对 $(a_i, b_i)$ 与 $(c_i, d_i)$ 不同)。

输出格式

输出满足对于每个 $i$，数对 $(a_i, b_i)$ 都在 $(c_i, d_i)$ 之前出现的平衡排列的数量。由于该数字可能非常大，请输出其对质数 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2 0

样例输出 1

1

样例输入 2

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

样例输出 2

2

说明

在第二个样例中，合法的排列为： $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$; $(1, 2), (1, 3), (2, 3), (1, 4), (2, 4), (3, 4)$。