Universal Cup Judging System

Universal Cup

実行時間制限: 3 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Sinulle annetaan tuntemattoman juurellisen puun $m$ syvyyssuuntaista läpikäyntijärjestystä (DFS-järjestystä).

Tarkastelemme juurellisia puita, joissa on $n$ solmua numeroituina $1$:stä $n$:ään ja joissa solmu $1$ on juuri. Puu on suuntaamaton ja yhtenäinen, ja siinä on täsmälleen $n - 1$ kaarta.

DFS:n määritelmä. Kiinteälle juurelliselle puulle DFS-järjestys saadaan seuraavasti:

  • Kaikki solmut ovat aluksi käymättömiä.
  • Aloita juuresta $1$, merkitse se käydyksi ja tulosta se.
  • Kun olet jossakin solmussa $v$, tarkastele kaikkia solmun $v$ lapsia juurellisessa puussa. Valitse sen lapset missä tahansa järjestyksessä. Jokaiselle valitulle lapselle $u$, joka on vielä käymätön, siirry solmuun $u$, merkitse se käydyksi, tulosta $u$ ja jatka DFS:ää solmusta $u$ samalla tavalla.

Kiinteälle puulle eri valinnat järjestyksestä, jossa kunkin solmun lapset käsitellään, voivat tuottaa erilaisia DFS-järjestyksiä. Kaikki DFS-järjestykset ovat lukujen $1, 2, \dots, n$ permutaatioita ja alkavat aina luvulla $1$.

Sinulle annetaan $m$ lukujen $1, 2, \dots, n$ permutaatiota, joista jokainen alkaa luvulla $1$. Sinulle kerrotaan, että jokainen niistä on saman juurellisen puun (jonka juuri on $1$) DFS-järjestys yllä määritellyssä mielessä (mahdollisesti käyttäen eri lapsijärjestysten valintoja eri DFS-suorituksissa).

Tehtäväsi on määrittää, kuinka moni eri juurellinen puu voisi tuottaa kaikki nämä $m$ DFS-järjestystä.

Kaksi juurellista puuta katsotaan erilaisiksi, jos niiden kaarijoukot ovat erilaiset.

Koska vastaus voi olla hyvin suuri, tulosta se modulo $10^9 + 7$.

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n, m \le 500$).

Jokainen seuraavista $m$ rivistä sisältää kokonaislukujen $1, 2, \dots, n$ permutaation $p_{k,1}, p_{k,2}, \dots, p_{k,n}$, joka kuvaa $k$:nnen DFS-järjestyksen.

Jokaisella $k$ kaikki luvut $p_{k,i}$ ovat erisuuria ja $p_{k,1} = 1$.

Tuloste

Tulosta yksi kokonaisluku: sellaisten juurellisten puiden lukumäärä, joiden solmujoukko on $1, 2, \dots, n$ ja juuri on $1$ ja joille jokainen annettu jono on kyseisen puun kelvollinen DFS-järjestys, modulo $10^9 + 7$.

Esimerkit

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.