Universal Cup Judging System

Universal Cup

Süre Sınırı: 3 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Сізге белгісіз түбірлі ағаштың тереңдігі бойынша іздеудің (DFS) $m$ реті берілген.

Біз $1$-ден $n$-ге дейін нөмірленген $n$ төбесі бар түбірлі ағаштарды қарастырамыз, мұндағы $1$-ші төбе — түбір. Ағаш бағытталмаған және байланысқан, әрі оның дәл $n - 1$ қыры бар.

DFS анықтамасы. Бекітілген түбірлі ағаш үшін DFS реті келесідей алынады:

  • Бастапқыда барлық төбелер қаралмаған күйде болады.
  • $1$-ші түбірден бастап, оны қаралды деп белгілеп, оны шығарыңыз.
  • Қандай да бір $v$ төбесінде тұрғанда, түбірлі ағаштағы $v$ төбесінің барлық балаларын қарастырыңыз. Оның балаларын кез келген ретпен таңдаңыз. Әлі қаралмаған әрбір таңдалған $u$ баласы үшін $u$-ға өтіп, оны қаралды деп белгілеп, $u$-ды шығарыңыз да, дәл солай $u$-дан DFS-ті жалғастырыңыз.

Бекітілген ағаш үшін әрбір төбенің балаларын өңдеу ретін әртүрлі таңдау әртүрлі DFS реттерін беруі мүмкін. Барлық DFS реттері $1, 2, \dots, n$ сандарының орын ауыстырулары болып табылады және әрқашан $1$-ден басталады.

Сізге әрқайсысы $1$-ден басталатын $1, 2, \dots, n$ сандарының $m$ орын ауыстыруы берілген. Олардың әрқайсысы жоғарыда анықталған мағынада бір ғана түбірлі ағаштың (түбірі $1$) DFS реті екені белгілі (әртүрлі DFS іске қосуларында балалар реті әртүрлі таңдалуы мүмкін).

Сіздің міндетіңіз — осы $m$ DFS ретінің барлығын бере алатын қанша әртүрлі түбірлі ағаш бар екенін анықтау.

Екі түбірлі ағаштың қырлар жиындары әртүрлі болса, олар әртүрлі деп есептеледі.

Жауап өте үлкен болуы мүмкін болғандықтан, оны $10^9 + 7$ модулі бойынша шығаруыңыз керек.

Кіріс деректер

Бірінші жолда екі бүтін сан $n$ және $m$ ($1 \le n, m \le 500$) берілген.

Келесі $m$ жолдың әрқайсысында $k$-шы DFS ретін сипаттайтын $1, 2, \dots, n$ бүтін сандарының $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ орын ауыстыруы берілген.

Әрбір $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.