Universal Cup Judging System

Universal Cup

Límite de tiempo: 3 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.