Perhatikan himpunan semua pasangan $(a,b)$ dengan $a$ dan $b$ memenuhi batasan $1 \le a < b \le n$. Suatu permutasi semua pasangan ini disebut seimbang jika dan hanya jika, untuk setiap $a$, $b$, dan $c$ yang memenuhi $1 \le a < b < c \le n$, pasangan $(a,c)$ berada di antara pasangan $(a,b)$ dan $(b,c)$ dalam permutasi tersebut. Artinya, ketiga pasangan itu muncul dalam permutasi dengan urutan $(a,b)$, $(a,c)$, $(b,c)$, atau dengan urutan $(b,c)$, $(a,c)$, $(a,b)$.

Selain itu, terdapat $m$ batasan tambahan pada permutasi tersebut. Batasan ke-$i$ menyatakan bahwa pasangan $(a_i,b_i)$ harus muncul sebelum pasangan $(c_i,d_i)$ dalam permutasi. Hitung banyaknya permutasi seimbang yang memenuhi $m$ batasan ini.

Masukan

Baris pertama masukan berisi bilangan bulat $n$ dan $m$ yang dipisahkan oleh spasi ($2 \le n \le 10$; $0 \le m \le 10$). Baris ke-$i$ dari $m$ baris berikutnya berisi bilangan bulat $a_i$, $b_i$, $c_i$, dan $d_i$ yang dipisahkan oleh spasi ($1 \le a_i < b_i \le n$; $1 \le c_i < d_i \le n$; pasangan $(a_i,b_i)$ dan $(c_i,d_i)$ berbeda).

Keluaran

Cetak banyaknya permutasi seimbang dengan $(a_i,b_i)$ muncul sebelum $(c_i,d_i)$ untuk setiap $i$. Karena bilangan ini dapat sangat besar, cetak nilainya modulo bilangan prima $998\,244\,353$.

Contoh

Masukan 1

2 0

Keluaran 1

1

Masukan 2

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

Keluaran 2

2

Catatan

Pada contoh kedua, permutasi-permutasinya adalah:

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

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