Considérons l'ensemble de tous les couples $(a, b)$ dont les éléments $a$ et $b$ satisfont $1 \le a < b \le n$. Une permutation de tous ces couples est dite équilibrée si et seulement si, pour tous $a$, $b$ et $c$ tels que $1 \le a < b < c \le n$, le couple $(a, c)$ se trouve entre les couples $(a, b)$ et $(b, c)$ dans la permutation. Autrement dit, ces trois couples apparaissent dans l'ordre $(a, b), (a, c), (b, c)$ ou dans l'ordre $(b, c), (a, c), (a, b)$.

De plus, la permutation est soumise à $m$ contraintes supplémentaires : la $i$-ième impose que le couple $(a_i, b_i)$ apparaisse avant le couple $(c_i, d_i)$. Calculez le nombre de permutations équilibrées qui satisfont ces $m$ contraintes.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $m$ séparés par un espace ($2 \le n \le 10$ ; $0 \le m \le 10$). La $i$-ième des $m$ lignes suivantes contient les entiers $a_i$, $b_i$, $c_i$ et $d_i$ séparés par des espaces ($1 \le a_i < b_i \le n$ ; $1 \le c_i < d_i \le n$ ; les couples $(a_i, b_i)$ et $(c_i, d_i)$ sont distincts).

Sortie

Affichez le nombre de permutations équilibrées dans lesquelles $(a_i, b_i)$ apparaît avant $(c_i, d_i)$ pour tout $i$. Ce nombre pouvant être très grand, affichez-le modulo le nombre premier $998\,244\,353$.

Exemples

Entrée 1

2 0

Sortie 1

1

Entrée 2

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

Sortie 2

2

Remarque

Dans le deuxième exemple, les permutations sont :

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

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