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