未知の根付き木の $m$ 個の深さ優先探索(DFS)順序が与えられます。
$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 順序をすべて生成しうる異なる根付き木が何通りあるかを求めることです。
$2$ つの根付き木は、それらの辺集合異なるときに異なるとみなされます。
答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。
入力
$1$ 行目には $2$ つの整数 $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