Þér eru gefnar $m$ dýptarleitarraðir (DFS-raðir) fyrir óþekkt rótarbundið tré.
Við skoðum rótarbundin tré með $n$ hnúta merkta frá $1$ til $n$, þar sem hnútur $1$ er rótin. Tréð er óstefnt og samanhangandi, og hefur nákvæmlega $n - 1$ leggi.
Skilgreining á DFS. Fyrir fast rótarbundið tré fæst DFS-röð á eftirfarandi hátt:
- Allir hnútar eru í upphafi óheimsóttir.
- Byrjaðu í rótinni $1$, merktu hana sem heimsótta og skrifaðu hana út.
- Þegar þú ert í einhverjum hnúti $v$ skaltu skoða öll börn $v$ í rótarbundna trénu. Veldu börn hans í hvaða röð sem er. Fyrir hvert valið barn $u$ sem enn er óheimsótt skaltu fara í $u$, merkja það sem heimsótt, skrifa út $u$ og halda DFS áfram frá $u$ á sama hátt.
Fyrir fast tré geta mismunandi val á röðinni sem börn hvers hnúts eru unnin í gefið mismunandi DFS-raðir. Allar DFS-raðir eru umraðanir á $1, 2, \dots, n$ og byrja alltaf á $1$.
Þér eru gefnar $m$ umraðanir á $1, 2, \dots, n$, sem hver um sig byrjar á $1$. Þér er sagt að hver þeirra sé DFS-röð á sama rótarbundna trénu (með rót $1$) í þeim skilningi sem skilgreindur er hér að ofan (mögulega með mismunandi vali á barnaröð í mismunandi DFS-keyrslum).
Verkefni þitt er að ákvarða hve mörg mismunandi rótarbundin tré gætu framkallað allar þessar $m$ DFS-raðir.
Tvö rótarbundin tré teljast ólík ef leggjamengi þeirra eru ólík.
Þar sem svarið getur verið mjög stórt ættirðu að skrifa það út modulo $10^9 + 7$.
Inntak
Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($1 \le n, m \le 500$).
Hver af næstu $m$ línum inniheldur umröðun $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ á heiltölunum $1, 2, \dots, n$, sem lýsir $k$-tu DFS-röðinni.
Fyrir hvert $k$ eru öll $p_{k,i}$ ólík og $p_{k,1} = 1$.
Úttak
Skrifið út eina heiltölu: fjölda rótarbundinna trjáa með hnútamengi $1, 2, \dots, n$ og rót $1$ þar sem hver gefin runa er gild DFS-röð þess trés, tekið modulo $10^9 + 7$.
Dæmi
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