اعتبر مجموعة جميع الأزواج $(a, b)$ التي يحقق فيها $a$ و$b$ القيد $1 \le a < b \le n$. يُسمّى ترتيب لجميع هذه الأزواج متوازنًا إذا وفقط إذا كان الزوج $(a, c)$ يقع بين الزوجين $(a, b)$ و$(b, c)$ في الترتيب، لكل $a$ و$b$ و$c$ تحقق $1 \le a < b < c \le n$. أي إن هذه الأزواج الثلاثة تظهر في الترتيب إما بالترتيب $(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)$.