Rozważmy zbiór wszystkich par $(a,b)$, w których $a$ i $b$ spełniają warunek $1 \le a < b \le n$. Permutację wszystkich tych par nazywamy zrównoważoną wtedy i tylko wtedy, gdy dla dowolnych $a$, $b$ i $c$ spełniających $1 \le a < b < c \le n$ para $(a,c)$ znajduje się w permutacji pomiędzy parami $(a,b)$ i $(b,c)$. Oznacza to, że te trzy pary występują w permutacji albo w kolejności $(a,b),(a,c),(b,c)$, albo w kolejności $(b,c),(a,c),(a,b)$.

Ponadto na permutację nałożono $m$ dodatkowych ograniczeń. $i$-te z nich mówi, że para $(a_i,b_i)$ powinna występować w permutacji przed parą $(c_i,d_i)$. Oblicz liczbę zrównoważonych permutacji spełniających te $m$ ograniczeń.

Wejście

Pierwszy wiersz wejścia zawiera oddzielone spacją liczby całkowite $n$ i $m$ ($2 \le n \le 10$; $0 \le m \le 10$). $i$-ty z kolejnych $m$ wierszy zawiera liczby całkowite $a_i$, $b_i$, $c_i$ i $d_i$, oddzielone spacjami ($1 \le a_i < b_i \le n$; $1 \le c_i < d_i \le n$; pary $(a_i,b_i)$ i $(c_i,d_i)$ są różne).

Wyjście

Wypisz liczbę zrównoważonych permutacji, w których $(a_i,b_i)$ występuje przed $(c_i,d_i)$ dla każdego $i$. Ponieważ ta liczba może być bardzo duża, wypisz ją modulo liczbę pierwszą $998\,244\,353$.

Przykład

Wejście 1

2 0

Wyjście 1

1

Wejście 2

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

Wyjście 2

2

Uwagi

W drugim przykładzie są to następujące permutacje:

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

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