토토로

길이가 $N$인 순열 $p_1, \dots, p_K$가 $K$개 주어진다.

$S$는 순열 $p_i$들을 유한 번 합성해서 얻을 수 있는 모든 순열의 집합이다. 두 순열 $\pi$와 $\tau$의 합성은 위치 $i$에서 $\pi(\tau(i))$의 값을 가진다. 예를 들어 $\pi = (1, 3, 2)$, $\tau = (2, 3, 1)$이면 $\pi \circ \tau = (3, 2, 1)$이다. 같은 순열을 여러 번 합성해도 된다.

$S$는 길이 $N$인 모든 순열의 집합에 포함되므로 유한 집합이다.

순열 $\pi$의 역전 수 $I(\pi)$는 $1 \le i < j \le N$이고 $\pi(i) > \pi(j)$인 순서쌍 $(i, j)$의 개수이다.

$\frac{1}{|S|}\sum_{\pi \in S} I(\pi)$를 구하라. 이 값은 기약분수 $\frac{A}{B}$로 나타낼 수 있으며, $B$는 $10^9 + 7$로 나누어떨어지지 않는다. $0 \le X < 10^9 + 7$이고 $X \cdot B \equiv A \pmod{10^9 + 7}$을 만족하는 $X$를 출력하라.

첫 줄에 자연수 $K$와 $N$이 주어진다.

이어지는 $K$개의 줄에는 순열 $p_i$가 $1$부터 $N$까지의 서로 다른 정수 $N$개를 공백으로 구분해 한 줄씩 주어진다.

답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 테스트 케이스 설명: $S = \{(2, 3, 1), (3, 1, 2), (1, 2, 3)\}$이다. 첫 번째 순열의 역전 수는 2이고, 두 번째 순열도 2이며, 항등 순열은 0이다. 평균은 $\frac{4}{3}$이고, 이를 $10^9 + 7$로 나눈 나머지가 출력값과 일치한다.

두 번째 테스트 케이스 설명: $S$가 $\{1, 2, 3, 4, 5\}$의 모든 순열의 집합과 같다는 것을 확인할 수 있다. 주어진 순열들을 합성하면 다른 모든 순열을 얻을 수 있다.

세 번째 테스트 케이스 설명: 이 경우 $|S| = 20$이고, 답은 $\frac{149}{10}$을 $10^9 + 7$로 나눈 나머지이다.