“Tonari no To to ro Totoro, To to ro Totoro”

Totoro 有 $K$ 个长度为 $N$ 的排列 $p_1, \dots, p_K$。

令 $S$ 为所有可以通过有限次复合排列 $p_i$ 得到的排列组成的集合。两个排列 $\pi$ 和 $\tau$ 的复合在位置 $i$ 处的值为 $\pi(\tau(i))$。例如，排列 $\pi = (1, 3, 2)$ 和 $\tau = (2, 3, 1)$ 的复合 $\pi \circ \tau = (3, 2, 1)$。允许重复使用相同的排列进行复合。

显然 $S$ 是一个有限集，因为它包含在所有长度为 $N$ 的排列集合中。

我们对集合 $S$ 中排列的平均逆序对数感兴趣。排列 $\pi$ 的逆序对数 $\mathcal{I}(\pi)$ 等于满足 $1 \le i < j \le N$ 且 $\pi(i) > \pi(j)$ 的有序数对 $(i, j)$ 的数量。

形式上，我们感兴趣的是 $\frac{1}{|S|} \sum_{\pi \in S} \mathcal{I}(\pi)$。可以证明，答案可以写成最简分数 $\frac{A}{B}$，其中 $B$ 不能被 $10^9 + 7$ 整除。请输出 $A \cdot B^{-1} \pmod{10^9 + 7}$，即满足 $0 \le X < 10^9 + 7$ 且 $X \cdot B \equiv A \pmod{10^9 + 7}$ 的整数 $X$。

输入格式

第一行包含自然数 $K$ 和 $N$。

接下来的 $K$ 行中，第 $i$ 行包含排列 $p_i$，表示为一个由 $1$ 到 $N$ 的 $N$ 个不同数字组成的序列，数字间以空格分隔。

输出格式

在唯一的一行中输出答案对 $10^9 + 7$ 取模的结果。

子任务

说明：如果可以将数字 $1, 2, \dots, n$ 排列成序列 $a_1, a_2, \dots, a_n$ 使得 $p(a_1) = a_2, p(a_2) = a_3, \dots, p(a_n) = a_1$ 成立，则称该排列为一个循环。

样例

样例输入 1

1 3
2 3 1

样例输出 1

333333337

说明 1

注意到 $S = \{(2, 3, 1), (3, 1, 2), (1, 2, 3)\}$。第一个排列有两个逆序对，第二个也有两个逆序对，最后一个是恒等排列，没有逆序对。因此平均逆序对数为 $\frac{4}{3}$，这对应于输出的模 $10^9 + 7$ 的结果。

样例输入 2

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

样例输出 2

5

说明 2

可以验证 $S$ 等于集合 $\{1, 2, 3, 4, 5\}$ 的所有排列组成的集合，即通过复合给定的排列可以得到所有其他排列。

样例输入 3

1 9
3 4 5 6 7 8 1 9 2

样例输出 3

300000017

说明 3

在本例中 $|S| = 20$，答案等于分数 $\frac{149}{10}$ 对 $10^9 + 7$ 取模的结果。