On vous donne $m$ ordres de parcours en profondeur (DFS) d'un arbre enraciné inconnu.
Nous considérons des arbres enracinés à $n$ sommets numérotés de $1$ à $n$, où le sommet $1$ est la racine. L'arbre est non orienté et connexe, et possède exactement $n - 1$ arêtes.
Définition du DFS. Pour un arbre enraciné fixé, un ordre DFS est obtenu comme suit :
- Tous les sommets sont initialement non visités.
- On commence à la racine $1$, on la marque comme visitée et on l'affiche.
- Lorsqu'on se trouve sur un sommet $v$, on considère tous les enfants de $v$ dans l'arbre enraciné. On choisit ses enfants dans un ordre quelconque. Pour chaque enfant choisi $u$ qui n'est pas encore visité, on se déplace en $u$, on le marque comme visité, on affiche $u$, et on poursuit le DFS à partir de $u$ de la même manière.
Pour un arbre fixé, différents choix de l'ordre dans lequel les enfants de chaque sommet sont traités peuvent produire différents ordres DFS. Tous les ordres DFS sont des permutations de $1, 2, \dots, n$ et commencent toujours par $1$.
On vous donne $m$ permutations de $1, 2, \dots, n$, commençant chacune par $1$. On vous indique que chacune d'elles est un ordre DFS du même arbre enraciné (de racine $1$) au sens défini ci-dessus (en utilisant éventuellement différents choix d'ordres des enfants pour différentes exécutions du DFS).
Votre tâche consiste à déterminer combien d'arbres enracinés différents pourraient produire tous ces $m$ ordres DFS.
Deux arbres enracinés sont considérés comme différents si leurs ensembles d'arêtes sont différents.
Comme la réponse peut être très grande, vous devez l'afficher modulo $10^9 + 7$.
Entrée
La première ligne contient deux entiers $n$ et $m$ ($1 \le n, m \le 500$).
Chacune des $m$ lignes suivantes contient une permutation $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ des entiers $1, 2, \dots, n$, décrivant le $k$-ième ordre DFS.
Pour tout $k$, tous les $p_{k,i}$ sont distincts et $p_{k,1} = 1$.
Sortie
Affichez un seul entier : le nombre d'arbres enracinés ayant pour ensemble de sommets $1, 2, \dots, n$ et pour racine $1$ pour lesquels chaque suite donnée est un ordre DFS valide de cet arbre, modulo $10^9 + 7$.
Exemples
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