순열 군

이 문제에서는 $n$개의 원소로 이루어진 순열을 다룬다. 순열은 1부터 $n$까지의 서로 다른 자연수 $n$개로 이루어진 수열이다.

순열 $a_1, a_2, \ldots, a_n$과 $b_1, b_2, \ldots, b_n$의 합성은 $ab = (a_{b_1}, a_{b_2}, \ldots, a_{b_n})$이다. 순열 $p_1, p_2, \ldots, p_n$에서 역전은 $i < j$이고 $p_i > p_j$인 인덱스 쌍 $(i, j)$를 뜻한다.

바이텍은 순열을 아주 좋아하며, 가장 좋아하는 순열을 $k$개 골랐다. 그는 이 순열들을 임의의 순서로 합성해서 얻을 수 있는 순열을 종이에 적기 시작했다. 그중 일부는 여러 번 사용할 수도 있다. 다만 같은 순열은 한 번만 적도록 신경 썼다.

종이가 금방 떨어졌다. 바이텍은 적을 수 있는 모든 순열의 역전 수가 평균 몇 개인지 궁금해졌다. 이 평균을 구하는 프로그램을 작성하라. 답은 출력 섹션에 설명한 대로 $10^9 + 7$로 나눈 나머지로 구한다.

첫 줄에 정수 $n$과 $k$가 주어진다 ($1 \le n, k \le 3000$). $n$은 순열의 길이이고, $k$는 바이텍이 좋아하는 순열의 개수다.

이어지는 $k$개 줄에 바이텍이 좋아하는 순열이 하나씩 주어진다. $i$번째 줄에는 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$이 주어지며 ($1 \le a_{i,j} \le n$), 한 줄의 $n$개 수는 모두 서로 다르다.

바이텍이 적을 수 있는 모든 순열의 평균 역전 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

정확히는 답을 기약분수 $p/q$라고 하자 ($q \neq 0$, $\gcd(p, q) = 1$). 이때 $p \times q^{-1} \bmod (10^9 + 7)$을 출력한다. 여기서 $q^{-1}$은 $q q^{-1} \equiv 1 \pmod{10^9 + 7}$을 만족하는 $1$ 이상 $10^9 + 6$ 이하의 유일한 정수다.

모든 유효한 테스트에서 기약분수의 분모는 $10^9 + 7$로 나누어떨어지지 않는다는 것이 증명되어 있다.

예제 설명: 첫 번째 경우 바이텍은 역전 0개인 $\{1, 2, 3\}$, 역전 2개인 $\{2, 3, 1\}$, 역전 2개인 $\{3, 1, 2\}$를 적는다. 평균은 $4/3$이다. $3^{-1} \equiv 333333336 \pmod{10^9 + 7}$이므로, 답은 $333333336 \times 4 \equiv 333333337 \pmod{10^9 + 7}$이다.

두 번째 경우 바이텍은 원소 5개로 이루어진 모든 순열을 적는다. 이들의 평균 역전 수는 정확히 5다.