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