Totoro

You are given $K$ permutations $p_1, \dots, p_K$ of length $N$.

Let $S$ be the set of all permutations that can be obtained by composing finitely many of the permutations $p_i$. The composition of permutations $\pi$ and $\tau$ has the element $\pi(\tau(i))$ at position $i$. For example, for $\pi = (1, 3, 2)$ and $\tau = (2, 3, 1)$, $\pi \circ \tau = (3, 2, 1)$. The same permutation may be composed multiple times.

Since $S$ is contained in the set of all permutations of length $N$, $S$ is finite.

The number of inversions $I(\pi)$ of a permutation $\pi$ is the number of pairs $1 \le i < j \le N$ with $\pi(i) > \pi(j)$.

Find $\frac{1}{|S|}\sum_{\pi \in S} I(\pi)$. This value can be written as an irreducible fraction $\frac{A}{B}$, where $B$ is not divisible by $10^9 + 7$. Print $X$ with $0 \le X < 10^9 + 7$ and $X \cdot B \equiv A \pmod{10^9 + 7}$.

The first line contains the natural numbers $K$ and $N$.

Each of the next $K$ lines contains the permutation $p_i$ as $N$ distinct integers from $1$ to $N$, separated by spaces.

Print the answer modulo $10^9 + 7$ on a single line.

Explanation of the first test case: $S = \{(2, 3, 1), (3, 1, 2), (1, 2, 3)\}$. The first permutation has two inversions, the second also has two, and the identity has none. The average is $\frac{4}{3}$, which matches the printed value modulo $10^9 + 7$.

Explanation of the second test case: one can check that $S$ equals the set of all permutations of $\{1, 2, 3, 4, 5\}$, so composing the given permutations yields every other permutation.

Explanation of the third test case: here $|S| = 20$, and the answer is the fraction $\frac{149}{10}$ modulo $10^9 + 7$.