Рассмотрим множество всех пар $(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)$.