נתונים לך $m$ סדרי חיפוש לעומק (DFS) של עץ מושרש לא ידוע.
אנו שוקלים עצים מושרשים עם $n$ צמתים הממוספרים מ-$1$ עד $n$, כאשר צומת $1$ הוא השורש. העץ הוא לא מכוון וקשיר, ויש לו בדיוק $n - 1$ קשתות.
הגדרת DFS. עבור עץ מושרש קבוע, סדר DFS מתקבל באופן הבא:
- כל הצמתים אינם מבוקרים בהתחלה.
- התחל בשורש $1$, סמן אותו כמבוקר והדפס אותו.
- כאשר אתה נמצא בצומת כלשהו $v$, שקול את כל הילדים של $v$ בעץ המושרש. בחר את ילדיו בכל סדר שהוא. עבור כל ילד נבחר $u$ שעדיין לא בוקר, עבור אל $u$, סמן אותו כמבוקר, הדפס את $u$, והמשך את ה-DFS מ-$u$ באותו אופן.
עבור עץ קבוע, בחירות שונות של הסדר שבו מעובדים הילדים של כל צומת עשויות ליצור סדרי DFS שונים. כל סדרי ה-DFS הם תמורות של $1, 2, \dots, n$ ותמיד מתחילים ב-$1$.
נתונות לך $m$ תמורות של $1, 2, \dots, n$, שכל אחת מהן מתחילה ב-$1$. נאמר לך שכל אחת מהן היא סדר DFS של אותו עץ מושרש (עם שורש $1$) במובן שהוגדר לעיל (ייתכן שתוך שימוש בבחירות שונות של סדרי ילדים עבור הרצות DFS שונות).
משימתך היא לקבוע כמה עצים מושרשים שונים יכולים לייצר את כל $m$ סדרי ה-DFS הללו.
שני עצים מושרשים נחשבים שונים אם קבוצות הקשתות שלהם שונות.
מכיוון שהתשובה עשויה להיות גדולה מאוד, עליך להדפיס אותה מודולו $10^9 + 7$.
קלט
השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$m$ ($1 \le n, m \le 500$).
כל אחת מ-$m$ השורות הבאות מכילה תמורה $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ של המספרים השלמים $1, 2, \dots, n$, המתארת את סדר ה-DFS ה-$k$.
עבור כל $k$, כל ה-$p_{k,i}$ שונים זה מזה ו-$p_{k,1} = 1$.
פלט
הדפס מספר שלם יחיד: מספר העצים המושרשים עם קבוצת צמתים $1, 2, \dots, n$ ושורש $1$ שעבורם כל סדרה נתונה היא סדר DFS חוקי של אותו עץ, מודולו $10^9 + 7$.
דוגמאות
3 2
1 2 3
1 3 2
1
4 1
1 2 3 4
5
5 2
1 2 3 4 5
1 2 4 3 5
3