Du får $m$ djupet-först-sökningsordningar (DFS-ordningar) för ett okänt rotat träd.
Vi betraktar rotade träd med $n$ hörn numrerade från $1$ till $n$, där hörn $1$ är roten. Trädet är oriktat och sammanhängande, och har exakt $n - 1$ kanter.
DFS-definition. För ett fixerat rotat träd erhålls en DFS-ordning enligt följande:
- Alla hörn är från början obesökta.
- Börja i roten $1$, markera den som besökt och skriv ut den.
- När du befinner dig i något hörn $v$, betrakta alla barn till $v$ i det rotade trädet. Välj dess barn i valfri ordning. För varje valt barn $u$ som fortfarande är obesökt, gå till $u$, markera det som besökt, skriv ut $u$ och fortsätt DFS från $u$ på samma sätt.
För ett fixerat träd kan olika val av ordningen i vilken barnen till varje hörn behandlas ge upphov till olika DFS-ordningar. Alla DFS-ordningar är permutationer av $1, 2, \dots, n$ och börjar alltid med $1$.
Du får $m$ permutationer av $1, 2, \dots, n$, som var och en börjar med $1$. Du får veta att var och en av dem är en DFS-ordning för samma rotade träd (med rot $1$) i den mening som definierats ovan (möjligen med olika val av barnordningar för olika DFS-körningar).
Din uppgift är att bestämma hur många olika rotade träd som skulle kunna ge upphov till alla dessa $m$ DFS-ordningar.
Två rotade träd betraktas som olika om deras kantmängder är olika.
Eftersom svaret kan bli mycket stort ska du skriva ut det modulo $10^9 + 7$.
Indata
Den första raden innehåller två heltal $n$ och $m$ ($1 \le n, m \le 500$).
Var och en av de följande $m$ raderna innehåller en permutation $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ av heltalen $1, 2, \dots, n$, som beskriver den $k$-te DFS-ordningen.
För varje $k$ är alla $p_{k,i}$ olika och $p_{k,1} = 1$.
Utdata
Skriv ut ett enda heltal: antalet rotade träd med hörnmängd $1, 2, \dots, n$ och rot $1$ för vilka varje given följd är en giltig DFS-ordning för det trädet, modulo $10^9 + 7$.
Exempel
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