この問題では、$n$ 要素の順列を扱います。各順列は $1$ から $n$ までの異なる自然数の列です。順列 $a_1, a_2, \dots, a_n$ と順列 $b_1, b_2, \dots, b_n$ の合成は、順列 $a_{b_1}, a_{b_2}, \dots, a_{b_n}$ と定義されます。順列 $p_1, p_2, \dots, p_n$ における転倒数とは、$i < j$ かつ $p_i > p_j$ を満たすインデックスの組 $(i, j)$ の個数のことです。

Bajtek は $n$ 要素の順列の大ファンです。彼はその中から $k$ 個の「お気に入り」の順列を持っています。彼は、これらのお気に入りの順列を（任意の順序で、またいくつかは繰り返し使用して）合成することで得られるすべての順列を紙に書き出すことにしました。その際、同じ順列を二度書き出さないように注意深く管理しました。

すぐに紙が足りなくなってしまったため、Bajtek は次のような疑問を抱きました。「もし彼が書き出せるすべての順列を書き出したとしたら、それらの転倒数の平均はいくつになるだろうか？」

この値を計算するプログラムを作成してください。具体的には、求める値を $10^9 + 7$ を法として出力してください（詳細は「出力」のセクションを参照してください）。

入力

入力の最初の行には、順列の長さ $n$ と Bajtek のお気に入りの順列の数 $k$ ($1 \le n, k \le 3000$) が含まれます。

続く $k$ 行には、それらの順列が記述されています。$i$ 番目の行には、$i$ 番目のお気に入りの順列である $n$ 個の異なる整数の列 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$) が含まれます。

出力

出力の唯一の行には、Bajtek が書き出し得るすべての順列の転倒数の平均値を $1\,000\,000\,007$ を法として出力してください。

形式的には、結果が $\frac{p}{q}$ （ただし $q \neq 0$ かつ $\gcd(p, q) = 1$）であるとき、$p \cdot q^{-1} \pmod{1\,000\,000\,007}$ を出力してください。ここで $q^{-1}$ は $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$ を満たす $\{1, 2, \dots, 1\,000\,000\,006\}$ の唯一の数です。

この問題の条件を満たすすべてのテストケースにおいて、結果は有理数であり、その既約分数形式の分母は $1\,000\,000\,007$ で割り切れないことが証明できます。

入出力例

入力 1

3 1
2 3 1

出力 1

333333337

入力 2

5 2
2 1 3 4 5
2 3 4 5 1

出力 2

5

注記

例 1 の説明：このテストケースでは、Bajtek は転倒数 0 の順列 $\{1, 2, 3\}$、転倒数 2 の順列 $\{2, 3, 1\}$、および同じく転倒数 2 の順列 $\{3, 1, 2\}$ を書き出します。したがって、転倒数の平均は $\frac{4}{3}$ です。$3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$ なので、$333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$ となります。

例 2 の説明：このテストケースでは、Bajtek は 5 要素のすべての順列を書き出します。それらの転倒数の平均がちょうど 5 であることは容易に示せます。