Permutation Group

This problem deals with permutations of $n$ elements. Each permutation is a sequence of $n$ distinct natural numbers from 1 to $n$.

The composition of permutations $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ is $ab = (a_{b_1}, a_{b_2}, \ldots, a_{b_n})$. An inversion in a permutation $p_1, p_2, \ldots, p_n$ is any index pair $(i, j)$ with $i < j$ and $p_i > p_j$.

Bytek is a big fan of permutations and has $k$ favorite ones. He began writing on paper every permutation that can be obtained by composing his favorite permutations in any order. Some of them may be used more than once. He made sure to write each permutation at most once.

He soon ran out of paper. Then he wondered: if he wrote all reachable permutations, what would be the average number of inversions in them?

Write a program that computes this value. Print it modulo $10^9 + 7$, as described in the Output section.

The first line contains two integers $n$ and $k$ ($1 \le n, k \le 3000$), the length of the permutations and the number of Bytek's favorite permutations.

Each of the next $k$ lines contains one favorite permutation. The $i$-th line holds $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($1 \le a_{i,j} \le n$), and all $n$ numbers in a line are distinct.

Print one integer: the average number of inversions over all permutations Bytek could write, modulo $10^9 + 7$.

Formally, let the answer be $p/q$ with $q \neq 0$ and $\gcd(p, q) = 1$. Print $p \times q^{-1} \bmod (10^9 + 7)$, where $q^{-1}$ is the unique integer from $1$ to $10^9 + 6$ that satisfies $q q^{-1} \equiv 1 \pmod{10^9 + 7}$.

It can be proven that for every valid test, the reduced denominator of the answer is not divisible by $10^9 + 7$.

Explanation of the example: in the first case, Bytek writes $\{1, 2, 3\}$ with zero inversions, $\{2, 3, 1\}$ with two inversions, and $\{3, 1, 2\}$ with two inversions. The average is $4/3$. Since $3^{-1} \equiv 333333336 \pmod{10^9 + 7}$, the answer is $333333336 \times 4 \equiv 333333337 \pmod{10^9 + 7}$.

In the second case, Bytek writes all permutations of 5 elements. Their average number of inversions is exactly 5.