Betrachte die Menge aller Paare $(a,b)$, deren Werte $a$ und $b$ die Bedingung $1 \le a < b \le n$ erfüllen. Eine Permutation aller dieser Paare heißt genau dann ausgeglichen, wenn für alle $a$, $b$ und $c$ mit $1 \le a < b < c \le n$ das Paar $(a,c)$ in der Permutation zwischen den Paaren $(a,b)$ und $(b,c)$ liegt. Das heißt, diese drei Paare erscheinen entweder in der Reihenfolge $(a,b), (a,c), (b,c)$ oder in der Reihenfolge $(b,c), (a,c), (a,b)$.

Außerdem gibt es $m$ zusätzliche Einschränkungen für die Permutation. Die $i$-te besagt, dass das Paar $(a_i,b_i)$ in der Permutation vor dem Paar $(c_i,d_i)$ erscheinen soll. Berechne die Anzahl der ausgeglichenen Permutationen, die diese $m$ Einschränkungen erfüllen.

Eingabe

Die erste Eingabezeile enthält die durch Leerzeichen getrennten ganzen Zahlen $n$ und $m$ ($2 \le n \le 10$; $0 \le m \le 10$). Die $i$-te der folgenden $m$ Zeilen enthält die durch Leerzeichen getrennten ganzen Zahlen $a_i$, $b_i$, $c_i$ und $d_i$ ($1 \le a_i < b_i \le n$; $1 \le c_i < d_i \le n$; die Paare $(a_i,b_i)$ und $(c_i,d_i)$ sind verschieden).

Ausgabe

Gib die Anzahl der ausgeglichenen Permutationen aus, in denen für jedes $i$ das Paar $(a_i,b_i)$ vor $(c_i,d_i)$ erscheint. Da diese Zahl sehr groß sein kann, gib sie modulo der Primzahl $998\,244\,353$ aus.

Beispiele

Eingabe 1

2 0

Ausgabe 1

1

Eingabe 2

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

Ausgabe 2

2

Hinweis

Im zweiten Beispiel sind die Permutationen:

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

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