Considere o conjunto de todos os pares $(a,b)$ em que $a$ e $b$ satisfazem a restrição $1 \le a < b \le n$. Uma permutação de todos esses pares é chamada de equilibrada se, e somente se, para quaisquer $a$, $b$ e $c$ que satisfaçam $1 \le a < b < c \le n$, o par $(a,c)$ estiver entre os pares $(a,b)$ e $(b,c)$ na permutação. Ou seja, esses três pares aparecem na permutação na ordem $(a,b)$, $(a,c)$, $(b,c)$ ou na ordem $(b,c)$, $(a,c)$, $(a,b)$.

Além disso, existem $m$ restrições adicionais sobre a permutação; a $i$-ésima delas estabelece que o par $(a_i,b_i)$ deve aparecer antes do par $(c_i,d_i)$ na permutação. Calcule o número de permutações equilibradas que satisfazem essas $m$ restrições.

Entrada

A primeira linha da entrada contém os inteiros $n$ e $m$, separados por um espaço ($2 \le n \le 10$; $0 \le m \le 10$). A $i$-ésima das $m$ linhas seguintes contém os inteiros $a_i$, $b_i$, $c_i$ e $d_i$, separados por espaços ($1 \le a_i < b_i \le n$; $1 \le c_i < d_i \le n$; os pares $(a_i,b_i)$ e $(c_i,d_i)$ são diferentes).

Saída

Imprima o número de permutações equilibradas em que $(a_i,b_i)$ aparece antes de $(c_i,d_i)$ para todo $i$. Como esse número pode ser muito grande, imprima-o módulo o número primo $998\,244\,353$.

Exemplos

Entrada 1

2 0

Saída 1

1

Entrada 2

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

Saída 2

2

Nota

No segundo exemplo, as permutações são:

$(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$;

$(1,2), (1,3), (2,3), (1,4), (2,4), (3,4)$.