พิจารณาเซตของคู่อันดับ $(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)$