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