Universal Cup Judging System

Universal Cup

時間限制: 3 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Dir sind $m$ Tiefensuche-Ordnungen (DFS-Ordnungen) eines unbekannten gewurzelten Baums gegeben.

Wir betrachten gewurzelte Bäume mit $n$ Knoten, die von $1$ bis $n$ nummeriert sind, wobei Knoten $1$ die Wurzel ist. Der Baum ist ungerichtet und zusammenhängend und hat genau $n - 1$ Kanten.

DFS-Definition. Für einen festen gewurzelten Baum erhält man eine DFS-Ordnung wie folgt:

  • Alle Knoten sind anfangs unbesucht.
  • Starte bei der Wurzel $1$, markiere sie als besucht und gib sie aus.
  • Wenn du dich an einem Knoten $v$ befindest, betrachte alle Kinder von $v$ im gewurzelten Baum. Wähle seine Kinder in beliebiger Reihenfolge. Gehe für jedes gewählte Kind $u$, das noch unbesucht ist, zu $u$, markiere es als besucht, gib $u$ aus und setze die DFS von $u$ aus auf dieselbe Weise fort.

Für einen festen Baum können unterschiedliche Wahlen der Reihenfolge, in der die Kinder jedes Knotens abgearbeitet werden, unterschiedliche DFS-Ordnungen erzeugen. Alle DFS-Ordnungen sind Permutationen von $1, 2, \dots, n$ und beginnen immer mit $1$.

Dir sind $m$ Permutationen von $1, 2, \dots, n$ gegeben, die jeweils mit $1$ beginnen. Es ist bekannt, dass jede von ihnen eine DFS-Ordnung desselben gewurzelten Baums (mit Wurzel $1$) im oben definierten Sinne ist (möglicherweise unter Verwendung unterschiedlicher Reihenfolgen der Kinder bei verschiedenen DFS-Durchläufen).

Deine Aufgabe ist es zu bestimmen, wie viele verschiedene gewurzelte Bäume alle diese $m$ DFS-Ordnungen erzeugen könnten.

Zwei gewurzelte Bäume gelten als verschieden, wenn ihre Kantenmengen verschieden sind.

Da die Antwort sehr groß sein kann, sollst du sie modulo $10^9 + 7$ ausgeben.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n, m \le 500$).

Jede der nächsten $m$ Zeilen enthält eine Permutation $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ der ganzen Zahlen $1, 2, \dots, n$, welche die $k$-te DFS-Ordnung beschreibt.

Für jedes $k$ sind alle $p_{k,i}$ paarweise verschieden und es gilt $p_{k,1} = 1$.

Ausgabe

Gib eine einzige ganze Zahl aus: die Anzahl der gewurzelten Bäume mit Knotenmenge $1, 2, \dots, n$ und Wurzel $1$, für die jede gegebene Folge eine gültige DFS-Ordnung dieses Baums ist, modulo $10^9 + 7$.

Beispiele

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.