In this problem, we will deal with $n$-element permutations. Each such permutation is a sequence of $n$ distinct natural numbers from $1$ to $n$ inclusive. The composition of a permutation $a_1, a_2, \dots, a_n$ with a permutation $b_1, b_2, \dots, b_n$ is the permutation $a_{b_1}, a_{b_2}, \dots, a_{b_n}$. An inversion in a permutation $p_1, p_2, \dots, p_n$ is any pair of indices $(i, j)$ such that $i < j$ and $p_i > p_j$.

Bajtek is a big fan of $n$-element permutations. He loves them so much that he even has $k$ favorites among them. He decided to start writing down on a piece of paper all the permutations that can be obtained by composing his favorite permutations (in any order and possibly using some of them multiple times), while meticulously ensuring that he does not write any permutation more than once.

It was no surprise that he ran out of paper quite quickly. Bajtek then wondered: if he were to write down all reachable permutations, what would be the average number of inversions they have?

Help him and write a program that calculates this value. More precisely, your task is to provide the requested value modulo $10^9 + 7$ (more on this in the Output section).

Input

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

The next $k$ lines contain these permutations. The $i$-th of these lines contains a sequence of $n$ distinct integers $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$), which is equal to the $i$-th favorite permutation of Bajtek.

Output

The single line of output should contain one integer equal to the average number of inversions among all permutations that Bajtek could write down, given modulo $1\,000\,000\,007$.

Formally, let the result be $\frac{p}{q}$, where $q \neq 0$ and $\gcd(p, q) = 1$. Then you should output the single number $p \cdot q^{-1} \pmod{1\,000\,000\,007}$, where $q^{-1}$ is the unique number from the set $\{1, 2, \dots, 1\,000\,000\,006\}$ such that $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$.

It can be proven that for all test cases satisfying the problem conditions, the result is a rational number whose denominator in irreducible form is not divisible by $1\,000\,000\,007$.

Examples

Input 1

3 1
2 3 1

Output 1

333333337

Input 2

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

Output 2

5

Note

In the first example test, Bajtek would write down the permutation $\{1, 2, 3\}$, which has zero inversions, $\{2, 3, 1\}$, which has two inversions, and $\{3, 1, 2\}$, which also has two inversions. The average number of inversions is therefore $\frac{4}{3}$. Since $3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$, we have $333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$.

In the second example test, Bajtek would write down all permutations of 5 elements. It is easy to show that, on average, they have exactly 5 inversions.