이 문제에서 우리는 $n$개의 원소를 가진 순열을 다룹니다. 각 순열은 $1$부터 $n$까지의 서로 다른 자연수 $n$개로 이루어진 수열입니다. 순열 $a_1, a_2, \dots, a_n$과 순열 $b_1, b_2, \dots, b_n$의 합성은 순열 $a_{b_1}, a_{b_2}, \dots, a_{b_n}$입니다. 순열 $p_1, p_2, \dots, p_n$에서의 반전(inversion)이란 $i < j$이면서 $p_i > p_j$를 만족하는 임의의 인덱스 쌍 $(i, j)$를 의미합니다.

Bajtek은 $n$개의 원소를 가진 순열의 열렬한 팬입니다. 그는 자신이 가장 좋아하는 $k$개의 순열을 가지고 있습니다. 그는 이 좋아하는 순열들을 (임의의 순서로, 그리고 일부는 여러 번 사용하여) 합성하여 얻을 수 있는 모든 순열을 종이에 적기로 했습니다. 이때, 어떤 순열도 두 번 이상 적지 않도록 주의했습니다.

얼마 지나지 않아 종이가 다 떨어졌고, Bajtek은 다음과 같은 질문을 떠올렸습니다: 만약 그가 얻을 수 있는 모든 순열을 적었다면, 그 순열들의 평균 반전 수는 얼마일까?

이 값을 계산하는 프로그램을 작성하세요. 더 정확히 말하면, 구하고자 하는 값을 $10^9 + 7$로 나눈 나머지를 출력해야 합니다 (자세한 내용은 출력 섹션 참조).

입력

첫 번째 줄에는 두 정수 $n$과 $k$ ($1 \le n, k \le 3000$)가 주어지며, 각각 순열의 길이와 Bajtek이 좋아하는 순열의 개수를 의미합니다.

이어지는 $k$개의 줄에는 각 순열이 주어집니다. $i$번째 줄에는 $i$번째로 좋아하는 순열인 $n$개의 서로 다른 정수 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$)이 주어집니다.

출력

출력의 유일한 줄에는 Bajtek이 적을 수 있는 모든 순열의 평균 반전 수를 $1\,000\,000\,007$로 나눈 나머지를 출력해야 합니다.

형식적으로, 결과가 $\frac{p}{q}$ ($q \neq 0$이고 $\gcd(p, q) = 1$)라고 할 때, $p \cdot q^{-1} \pmod{1\,000\,000\,007}$을 출력해야 합니다. 여기서 $q^{-1}$은 $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$을 만족하는 $\{1, 2, \dots, 1\,000\,000\,006\}$ 내의 유일한 수입니다.

문제의 조건을 만족하는 모든 테스트 케이스에서 결과는 기약분수로 나타냈을 때 분모가 $1\,000\,000\,007$로 나누어떨어지지 않는 유리수임이 증명되어 있습니다.

예제

입력 1

3 1
2 3 1

출력 1

333333337

입력 2

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

출력 2

5

참고

첫 번째 예제에서 Bajtek은 반전이 0개인 순열 $\{1, 2, 3\}$, 반전이 2개인 $\{2, 3, 1\}$, 그리고 반전이 2개인 $\{3, 1, 2\}$를 적게 됩니다. 따라서 평균 반전 수는 $\frac{4}{3}$입니다. $3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$이므로, $333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$이 됩니다.

두 번째 예제에서 Bajtek은 5개의 원소로 이루어진 모든 순열을 적게 됩니다. 이 순열들의 평균 반전 수는 정확히 5임을 쉽게 보일 수 있습니다.