Universal Cup Judging System

Universal Cup

حد الوقت: 3 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Вам даны $m$ порядков обхода в глубину (DFS) неизвестного корневого дерева.

Мы рассматриваем корневые деревья с $n$ вершинами, пронумерованными от $1$ до $n$, где вершина $1$ является корнем. Дерево неориентированное и связное, и содержит ровно $n - 1$ рёбер.

Определение DFS. Для фиксированного корневого дерева порядок DFS получается следующим образом:

  • Изначально все вершины являются непосещёнными.
  • Начните в корне $1$, отметьте его как посещённый и выведите его.
  • Находясь в некоторой вершине $v$, рассмотрите всех сыновей вершины $v$ в корневом дереве. Выберите её сыновей в произвольном порядке. Для каждого выбранного сына $u$, который всё ещё не посещён, перейдите в $u$, отметьте его как посещённый, выведите $u$ и продолжите DFS из $u$ таким же образом.

Для фиксированного дерева различный выбор порядка обработки сыновей каждой вершины может приводить к различным порядкам DFS. Все порядки DFS являются перестановками чисел $1, 2, \dots, n$ и всегда начинаются с $1$.

Вам даны $m$ перестановок чисел $1, 2, \dots, n$, каждая из которых начинается с $1$. Известно, что каждая из них является порядком DFS одного и того же корневого дерева (с корнем $1$) в определённом выше смысле (возможно, при различном выборе порядка сыновей в разных запусках DFS).

Ваша задача — определить, сколько различных корневых деревьев могут породить все эти $m$ порядков DFS.

Два корневых дерева считаются различными, если различаются множества их рёбер.

Поскольку ответ может быть очень большим, выведите его по модулю $10^9 + 7$.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 500$).

Каждая из следующих $m$ строк содержит перестановку $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ целых чисел $1, 2, \dots, n$, описывающую $k$-й порядок DFS.

Для каждого $k$ все $p_{k,i}$ попарно различны и $p_{k,1} = 1$.

Выходные данные

Выведите одно целое число: количество корневых деревьев с множеством вершин $1, 2, \dots, n$ и корнем $1$, для которых каждая заданная последовательность является допустимым порядком DFS этого дерева, по модулю $10^9 + 7$.

Примеры

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.