Considera el conjunto de todos los pares $(a,b)$ cuyos valores $a$ y $b$ satisfacen la condición $1 \le a < b \le n$. Una permutación de todos estos pares se llama equilibrada si y solo si, para cualesquiera $a$, $b$ y $c$ que satisfagan $1 \le a < b < c \le n$, el par $(a,c)$ se encuentra entre los pares $(a,b)$ y $(b,c)$ en la permutación. Es decir, esos tres pares aparecen en la permutación en el orden $(a,b)$, $(a,c)$, $(b,c)$, o en el orden $(b,c)$, $(a,c)$, $(a,b)$.

Además, hay $m$ restricciones adicionales sobre la permutación; la $i$-ésima establece que el par $(a_i,b_i)$ debe aparecer antes que el par $(c_i,d_i)$ en la permutación. Calcula el número de permutaciones equilibradas que satisfacen estas $m$ restricciones.

Entrada

La primera línea de la entrada contiene los enteros $n$ y $m$ separados por un espacio ($2 \le n \le 10$; $0 \le m \le 10$). La $i$-ésima de las siguientes $m$ líneas contiene los enteros $a_i$, $b_i$, $c_i$ y $d_i$ separados por espacios ($1 \le a_i < b_i \le n$; $1 \le c_i < d_i \le n$; los pares $(a_i,b_i)$ y $(c_i,d_i)$ son distintos).

Salida

Imprime el número de permutaciones equilibradas en las que $(a_i,b_i)$ aparece antes que $(c_i,d_i)$ para todo $i$. Como este número puede ser muy grande, imprímelo módulo el número primo $998\,244\,353$.

Ejemplos

Entrada 1

2 0

Salida 1

1

Entrada 2

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

Salida 2

2

Nota

En el segundo ejemplo, las permutaciones son:

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

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