畀定一棵未知有根樹嘅 $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