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