נבחן את קבוצת כל הזוגות $(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)$.