알려지지 않은 루트 있는 트리의 깊이 우선 탐색(DFS) 순서 $m$개가 주어집니다.
$1$부터 $n$까지 번호가 매겨진 $n$개의 정점을 가지며 정점 $1$이 루트인 루트 있는 트리를 생각합니다. 이 트리는 무방향 연결 그래프이며, 정확히 $n - 1$개의 간선을 가집니다.
DFS의 정의. 고정된 루트 있는 트리에 대해, DFS 순서는 다음과 같이 얻어집니다:
- 모든 정점은 처음에 방문하지 않은 상태입니다.
- 루트 $1$에서 시작하여 방문했다고 표시하고 이를 출력합니다.
- 어떤 정점 $v$에 있을 때, 루트 있는 트리에서 $v$의 모든 자식 정점을 고려합니다. 자식 정점들을 임의의 순서로 선택합니다. 선택된 각 자식 정점 $u$가 아직 방문하지 않은 상태라면, $u$로 이동하여 방문했다고 표시하고 $u$를 출력한 뒤, 같은 방식으로 $u$에서부터 DFS를 계속 진행합니다.
고정된 트리에 대해 각 정점의 자식들을 처리하는 순서의 선택이 달라지면 서로 다른 DFS 순서가 만들어질 수 있습니다. 모든 DFS 순서는 $1, 2, \dots, n$의 순열이며 항상 $1$로 시작합니다.
각각 $1$로 시작하는 $1, 2, \dots, n$의 순열 $m$개가 주어집니다. 이 순열들은 모두 위에서 정의한 의미에서 동일한 루트 있는 트리(루트는 $1$)의 DFS 순서임이 알려져 있습니다(서로 다른 DFS 실행마다 자식 순서의 선택은 다를 수 있습니다).
여러분의 과제는 이 $m$개의 DFS 순서를 모두 만들어낼 수 있는 서로 다른 루트 있는 트리가 몇 개인지 구하는 것입니다.
두 루트 있는 트리는 간선 집합이 다를 때 서로 다른 것으로 간주합니다.
답이 매우 클 수 있으므로, $10^9 + 7$로 나눈 나머지를 출력해야 합니다.
입력
첫 번째 줄에 두 정수 $n$과 $m$($1 \le n, m \le 500$)이 주어집니다.
다음 $m$개의 줄에는 각각 $k$번째 DFS 순서를 설명하는 정수 $1, 2, \dots, n$의 순열 $p_{k,1}, p_{k,2}, \dots, p_{k,n}$이 주어집니다.
모든 $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