Du får oppgitt $m$ dybde-først-søk-rekkefølger (DFS-rekkefølger) av et ukjent rotfestet tre.
Vi betrakter rotfestede trær med $n$ noder merket fra $1$ til $n$, der node $1$ er roten. Treet er urettet og sammenhengende, og har nøyaktig $n - 1$ kanter.
DFS-definisjon. For et fast rotfestet tre oppnås en DFS-rekkefølge på følgende måte:
- Alle noder er til å begynne med ubesøkte.
- Start ved roten $1$, marker den som besøkt og skriv den ut.
- Når du er ved en node $v$, betrakt alle barna til $v$ i det rotfestede treet. Velg barna i en hvilken som helst rekkefølge. For hvert valgte barn $u$ som fremdeles er ubesøkt, gå til $u$, marker det som besøkt, skriv ut $u$, og fortsett DFS fra $u$ på samme måte.
For et fast tre kan ulike valg av rekkefølgen barna til hver node behandles i, gi ulike DFS-rekkefølger. Alle DFS-rekkefølger er permutasjoner av $1, 2, \dots, n$ og starter alltid med $1$.
Du får oppgitt $m$ permutasjoner av $1, 2, \dots, n$, som hver starter med $1$. Du får vite at hver av dem er en DFS-rekkefølge av det samme rotfestede treet (med rot $1$) i den betydningen som er definert ovenfor (muligens med ulike valg av barnerekkefølger for ulike DFS-kjøringer).
Din oppgave er å bestemme hvor mange ulike rotfestede trær som kan produsere alle disse $m$ DFS-rekkefølgene.
To rotfestede trær regnes som ulike hvis kantmengdene deres er ulike.
Fordi svaret kan være svært stort, skal du skrive det ut modulo $10^9 + 7$.
Inndata
Den første linjen inneholder to heltall $n$ og $m$ ($1 \le n, m \le 500$).
Hver av de neste $m$ linjene inneholder en permutasjon $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ av heltallene $1, 2, \dots, n$, som beskriver den $k$-te DFS-rekkefølgen.
For hver $k$ er alle $p_{k,i}$ forskjellige og $p_{k,1} = 1$.
Utdata
Skriv ut et enkelt heltall: antallet rotfestede trær med nodemengde $1, 2, \dots, n$ og rot $1$ der hver oppgitte følge er en gyldig DFS-rekkefølge for dette treet, tatt modulo $10^9 + 7$.
Eksempler
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