Розглянемо множину всіх пар $(a,b)$, де $a$ і $b$ задовольняють умову $1 \le a < b \le n$. Перестановка всіх цих пар називається збалансованою тоді й лише тоді, коли для будь-яких $a$, $b$ та $c$, що задовольняють $1 \le a < b < c \le n$, пара $(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$). $i$-й із наступних $m$ рядків містить цілі числа $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)$ різні).

Вихідні дані

Виведіть кількість збалансованих перестановок, у яких $(a_i,b_i)$ з'являється раніше за $(c_i,d_i)$ для кожного $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)$.