이브이

이브이는 다양한 방식으로 진화할 수 있다. 예를 들어 진화의 돌 중 하나에 가까이 다가가면 진화한다.

진화의 돌은 서로 다른 $n$개가 있고, 번호는 1부터 $n$까지이다. 각 돌은 $k$개의 조각으로 나뉘어 있다. 이브이는 모든 조각을 $k$개의 스택으로 묶었고, 스택 번호는 1부터 $k$까지이다. 각 스택에는 서로 다른 돌에서 나온 조각이 정확히 $n$개씩 들어 있으므로, 각 스택은 돌 조각들의 순열로 볼 수 있다.

이브이는 다음 작업을 $k \times n$번 수행한다. 비어 있지 않은 스택 하나를 골라 가장 위의 조각을 떼어 내고, 이를 처음에는 비어 있는 수열의 끝에 붙인다. 스택을 고르는 순서가 한 번이라도 다르면 두 결합 방식은 서로 다른 것으로 본다. 이 과정이 끝난 뒤 수열에 같은 돌의 조각이 $k$개 이웃해 있으면 이브이는 우연히 진화할 수 있다. 길이가 $k$인 어떤 구간도 같은 돌의 조각만으로 이루어지지 않는 결합 방식을 좋은 방식이라고 한다.

$f(i, j)$는 번호가 $i$부터 $j$까지인 스택들을 결합하는 좋은 방식의 수이다. 길이가 $\ell$인 구간을 고려할 때는 이브이가 작업을 $\ell \times n$번만 수행한다고 가정하며, 길이가 $\ell$인 구간이 같은 돌의 조각만으로 이루어지는 것은 금지한다.

다음 값을 구하라.

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

그런데 이브이가 작업 전에 각 스택을 섞었던 것이 밝혀졌다. 따라서 각 스택은 조각들의 무작위 순열이다. 입력으로 주어지는 각 순열은 $n!$가지 순열 전체에서 같은 확률로, 그리고 다른 순열과 독립적으로 뽑힌 것이다.

첫째 줄에 스택의 개수 $k$와 각 스택의 조각 수 $n$이 주어진다 ($2 \le k, n \le 300$). 이어서 $k$개의 줄에 각각 $n$개의 정수가 주어진다. $i$번째 줄의 $j$번째 수 $a_{i,j}$는 $i$번째 스택의 위에서 $j$번째 조각이 속한 돌의 번호이며, $1 \le a_{i,j} \le n$이다. 같은 줄에서 $j \ne l$이면 $a_{i,j} \ne a_{i,l}$이다.

문제에서 정의한 합의 값을 출력한다.

첫 번째 예제에서 $f(1, 3)$을 계산해 보자. 이브이에게는 돌 조각이 담긴 스택이 세 개 있다.

좋은 결합 방식 중 하나는 다음과 같다.

다음 방식은 3이 세 번 연속으로 나오므로 좋지 않다.

첫 번째 예제에서 $f(1, 2) = 8$, $f(1, 3) = 1446$, $f(2, 3) = 10$이다. 두 번째 예제에서 $f(1, 2) = 2$, $f(1, 3) = 66$, $f(1, 4) = 2328$, $f(2, 3) = 2$, $f(2, 4) = 66$, $f(3, 4) = 2$이다.