Ti vengono dati $m$ ordini di visita in profondità (DFS) di un albero radicato sconosciuto.
Consideriamo alberi radicati con $n$ vertici etichettati da $1$ a $n$, dove il vertice $1$ è la radice. L'albero è non orientato e connesso, e ha esattamente $n - 1$ archi.
Definizione di DFS. Per un albero radicato fissato, un ordine DFS si ottiene come segue:
- Tutti i vertici sono inizialmente non visitati.
- Inizia dalla radice $1$, contrassegnala come visitata e stampala.
- Quando ti trovi in un vertice $v$, considera tutti i figli di $v$ nell'albero radicato. Scegli i suoi figli in qualsiasi ordine. Per ciascun figlio scelto $u$ che è ancora non visitato, vai in $u$, contrassegnalo come visitato, stampa $u$ e continua la DFS da $u$ allo stesso modo.
Per un albero fissato, scelte diverse dell'ordine in cui vengono elaborati i figli di ciascun vertice possono produrre ordini DFS diversi. Tutti gli ordini DFS sono permutazioni di $1, 2, \dots, n$ e iniziano sempre con $1$.
Ti vengono date $m$ permutazioni di $1, 2, \dots, n$, ciascuna che inizia con $1$. Ti viene detto che ciascuna di esse è un ordine DFS dello stesso albero radicato (con radice $1$) nel senso definito sopra (eventualmente utilizzando scelte diverse degli ordini dei figli per diverse esecuzioni della DFS).
Il tuo compito è determinare quanti diversi alberi radicati potrebbero produrre tutti questi $m$ ordini DFS.
Due alberi radicati sono considerati diversi se i loro insiemi di archi sono diversi.
Poiché la risposta può essere molto grande, devi stamparla modulo $10^9 + 7$.
Input
La prima riga contiene due interi $n$ e $m$ ($1 \le n, m \le 500$).
Ciascuna delle successive $m$ righe contiene una permutazione $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ degli interi $1, 2, \dots, n$, che descrive il $k$-esimo ordine DFS.
Per ogni $k$, tutti i $p_{k,i}$ sono distinti e $p_{k,1} = 1$.
Output
Stampa un singolo intero: il numero di alberi radicati con insieme dei vertici $1, 2, \dots, n$ e radice $1$ per i quali ogni sequenza data è un ordine DFS valido di quell'albero, modulo $10^9 + 7$.
Esempi
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