Universal Cup Judging System

Universal Cup

Límite de tiempo: 3 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

נתונים לך $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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.