給定一棵未知有根樹的 $m$ 個深度優先搜尋(DFS)序。
我們考慮包含 $n$ 個頂點(編號從 $1$ 到 $n$)的有根樹,其中頂點 $1$ 是根。該樹是無向連通的,並且恰好有 $n - 1$ 條邊。
DFS 的定義。 對於一棵固定的有根樹,其 DFS 序透過以下方式獲得:
- 所有頂點初始時均為未造訪狀態。
- 從根節點 $1$ 開始,將其標記為已造訪並輸出它。
- 當你位於某個頂點 $v$ 時,考慮該有根樹中 $v$ 的所有子節點。以任意順序選擇它的子節點。對於每個選定的且仍未造訪的子節點 $u$,移動到 $u$,將其標記為已造訪,輸出 $u$,並以相同的方式從 $u$ 繼續進行 DFS。
對於一棵固定的樹,處理每個頂點子節點的不同順序可能會產生不同的 DFS 序。所有的 DFS 序都是 $1, 2, \dots, n$ 的排列,並且總是以 $1$ 開頭。
給定 $m$ 個 $1, 2, \dots, n$ 的排列,每個排列都以 $1$ 開頭。已知它們都是同一棵有根樹(以 $1$ 為根)在上述定義意義下的 DFS 序(在不同的 DFS 過程中可能使用了不同的子節點順序)。
你的任務是確定有多少棵不同的有根樹可以產生所有這 $m$ 個 DFS 序。
如果兩棵有根樹的邊集不同,則認為它們是不同的。
由於答案可能非常大,你應該輸出其對 $10^9 + 7$ 取模後的結果。
輸入格式
第一行包含兩個整數 $n$ 和 $m$($1 \le n, m \le 500$)。
接下來的 $m$ 行,每行包含一個整數 $1, 2, \dots, n$ 的排列 $p_{k,1}, p_{k,2}, \dots, p_{k,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