在本題中，我們將探討 $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$ 和 $k$ ($1 \le n, k \le 3000$)，分別代表排列的長度和 Bajtek 最喜歡的排列數量。

接下來的 $k$ 行包含這些排列。第 $i$ 行包含一個由 $n$ 個不同整數組成的序列 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$)，代表 Bajtek 第 $i$ 個最喜歡的排列。

輸出格式

輸出的唯一一行應包含一個整數，等於 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}$ 是集合 $\{1, 2, \dots, 1\,000\,000\,006\}$ 中唯一滿足 $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$ 的數。

可以證明，對於所有滿足題目條件的測試資料，結果皆為有理數，且其最簡分數形式的分母不能被 $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

說明

在第一個範例測試中，Bajtek 會寫下排列 $\{1, 2, 3\}$（有 0 個逆序對）、$\{2, 3, 1\}$（有 2 個逆序對）以及 $\{3, 1, 2\}$（有 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}$。

在第二個範例測試中，Bajtek 會寫下所有 5 個元素的排列。很容易證明，它們平均恰好有 5 個逆序對。