Eevee

Eevee can evolve in various ways. For instance, it evolves when it comes close to one of the evolution stones.

There are $n$ different evolution stones, numbered from 1 to $n$. Each stone is split into $k$ fragments. Eevee grouped all the fragments into $k$ stacks, numbered from 1 to $k$. Each stack contains exactly $n$ fragments, each from a different stone, so each stack can be viewed as a permutation of the stone fragments.

Eevee performs the following operation $k \times n$ times. It picks a non-empty stack, removes its topmost fragment, and appends it to the end of a sequence that starts empty. Two ways of combining the stacks are different if at some step a different stack index is chosen. After the process, if the sequence contains $k$ neighboring fragments of the same stone, Eevee can evolve by accident. A way to combine the stacks is called good if no interval of length $k$ contains only fragments of the same stone.

Let $f(i, j)$ be the number of good ways to combine the stacks with indices in the range $[i, j]$. For an interval of length $\ell$, we assume Eevee performs the operation only $\ell \times n$ times, and no interval of length $\ell$ may contain only fragments of the same stone.

Compute

$\left(\sum_{i=1}^{k}\sum_{j=i+1}^{k}f(i,j)\right) \bmod (10^9+7)$

However, it turned out that Eevee shuffled each stack before the process. So each stack contains a random permutation of its fragments. Each input permutation is chosen uniformly from all $n!$ permutations, independently of the others.

The first line contains two integers $k$ and $n$ ($2 \le k, n \le 300$), the number of stacks and the number of fragments in each stack. Each of the next $k$ lines contains $n$ integers. The $j$-th number in the $i$-th line is $a_{i,j}$ ($1 \le a_{i,j} \le n$, and $a_{i,j} \ne a_{i,l}$ for $j \ne l$), the $j$-th number from the top of the $i$-th stack.

Output the value of the sum described in the problem statement.

Consider calculating $f(1, 3)$ in the first sample. Eevee has three stacks of the stone fragments:

One of the good ways to combine them is as follows:

The following one is not good, as it contains three 3s in a row:

In the first sample $f(1, 2) = 8$, $f(1, 3) = 1446$, and $f(2, 3) = 10$. In the second sample $f(1, 2) = 2$, $f(1, 3) = 66$, $f(1, 4) = 2328$, $f(2, 3) = 2$, $f(2, 4) = 66$, and $f(3, 4) = 2$.