考慮所有滿足 $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)$。