Universal Cup Judging System

Universal Cup

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Du får $m$ djupet-först-sökningsordningar (DFS-ordningar) för ett okänt rotat träd.

Vi betraktar rotade träd med $n$ hörn numrerade från $1$ till $n$, där hörn $1$ är roten. Trädet är oriktat och sammanhängande, och har exakt $n - 1$ kanter.

DFS-definition. För ett fixerat rotat träd erhålls en DFS-ordning enligt följande:

  • Alla hörn är från början obesökta.
  • Börja i roten $1$, markera den som besökt och skriv ut den.
  • När du befinner dig i något hörn $v$, betrakta alla barn till $v$ i det rotade trädet. Välj dess barn i valfri ordning. För varje valt barn $u$ som fortfarande är obesökt, gå till $u$, markera det som besökt, skriv ut $u$ och fortsätt DFS från $u$ på samma sätt.

För ett fixerat träd kan olika val av ordningen i vilken barnen till varje hörn behandlas ge upphov till olika DFS-ordningar. Alla DFS-ordningar är permutationer av $1, 2, \dots, n$ och börjar alltid med $1$.

Du får $m$ permutationer av $1, 2, \dots, n$, som var och en börjar med $1$. Du får veta att var och en av dem är en DFS-ordning för samma rotade träd (med rot $1$) i den mening som definierats ovan (möjligen med olika val av barnordningar för olika DFS-körningar).

Din uppgift är att bestämma hur många olika rotade träd som skulle kunna ge upphov till alla dessa $m$ DFS-ordningar.

Två rotade träd betraktas som olika om deras kantmängder är olika.

Eftersom svaret kan bli mycket stort ska du skriva ut det modulo $10^9 + 7$.

Indata

Den första raden innehåller två heltal $n$ och $m$ ($1 \le n, m \le 500$).

Var och en av de följande $m$ raderna innehåller en permutation $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ av heltalen $1, 2, \dots, n$, som beskriver den $k$-te DFS-ordningen.

För varje $k$ är alla $p_{k,i}$ olika och $p_{k,1} = 1$.

Utdata

Skriv ut ett enda heltal: antalet rotade träd med hörnmängd $1, 2, \dots, n$ och rot $1$ för vilka varje given följd är en giltig DFS-ordning för det trädet, modulo $10^9 + 7$.

Exempel

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.