在本题中，我们将研究 $n$ 阶排列。每个这样的排列都是由 $1$ 到 $n$ 的 $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。