Вам даны $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