Danych jest $m$ porządków przeszukiwania w głąb (DFS) pewnego nieznanego drzewa ukorzenionego.
Rozważamy drzewa ukorzenione o $n$ wierzchołkach ponumerowanych od $1$ do $n$, gdzie wierzchołek $1$ jest korzeniem. Drzewo jest nieskierowane i spójne oraz ma dokładnie $n - 1$ krawędzi.
Definicja DFS. Dla ustalonego drzewa ukorzenionego porządek DFS otrzymujemy w następujący sposób:
- Początkowo wszystkie wierzchołki są nieodwiedzone.
- Zacznij w korzeniu $1$, oznacz go jako odwiedzony i wypisz go.
- Będąc w pewnym wierzchołku $v$, rozważ wszystkich synów wierzchołka $v$ w drzewie ukorzenionym. Wybierz jego synów w dowolnej kolejności. Dla każdego wybranego syna $u$, który wciąż jest nieodwiedzony, przejdź do $u$, oznacz go jako odwiedzonego, wypisz $u$ i kontynuuj DFS z wierzchołka $u$ w ten sam sposób.
Dla ustalonego drzewa różne wybory kolejności przetwarzania synów każdego wierzchołka mogą dawać różne porządki DFS. Wszystkie porządki DFS są permutacjami liczb $1, 2, \dots, n$ i zawsze zaczynają się od $1$.
Danych jest $m$ permutacji liczb $1, 2, \dots, n$, z których każda zaczyna się od $1$. Wiadomo, że każda z nich jest porządkiem DFS tego samego drzewa ukorzenionego (o korzeniu $1$) w sensie zdefiniowanym powyżej (być może przy użyciu różnej kolejności synów w różnych uruchomieniach DFS).
Twoim zadaniem jest określenie, ile różnych drzew ukorzenionych mogłoby wygenerować wszystkie te $m$ porządków DFS.
Dwa drzewa ukorzenione uważamy za różne, jeśli różnią się zbiorami krawędzi.
Ponieważ odpowiedź może być bardzo duża, należy wypisać ją modulo $10^9 + 7$.
Wejście
Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 500$).
Każdy z kolejnych $m$ wierszy zawiera permutację $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ liczb całkowitych $1, 2, \dots, n$, opisującą $k$-ty porządek DFS.
Dla każdego $k$ wszystkie liczby $p_{k,i}$ są parami różne oraz $p_{k,1} = 1$.
Wyjście
Wypisz jedną liczbę całkowitą: liczbę drzew ukorzenionych o zbiorze wierzchołków $1, 2, \dots, n$ i korzeniu $1$, dla których każdy podany ciąg jest poprawnym porządkiem DFS tego drzewa, wziętą modulo $10^9 + 7$.
Przykłady
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