$N$ 장의 종이가 있으며, $1$부터 $N$까지의 정수로 번호가 매겨져 있습니다. 각 종이에는 $K$개의 정수가 적혀 있으며, $i$번째 종이에는 $v_{i,1}, v_{i,2}, \dots, v_{i,K}$가 적혀 있습니다.

각 종이에서 정수를 하나씩 선택하여 수열 $a_i$를 만듭니다. 여기서 $i$번째 정수는 $i$번째 종이에서 선택합니다. 이러한 수열을 만드는 방법은 총 $K^N$가지가 있습니다. 이 중 비내림차순인 수열은 몇 개입니까? 수열이 비내림차순이라는 것은 모든 $1 \le i \le N - 1$에 대하여 $a_i \le a_{i+1}$을 만족함을 의미합니다.

정답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하십시오.

입력

첫 번째 줄에는 두 정수 $N$과 $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$)가 주어집니다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 $K$개의 정수 $v_{i,1}, v_{i,2}, \dots, v_{i,K}$ ($1 \le v_{i,1} < v_{i,2} < \dots < v_{i,K} \le 10^9$)가 주어집니다.

출력

비내림차순 수열의 개수를 $10^9 + 7$로 나눈 나머지를 출력하십시오.

예제

예제 입력 1

2 2
2 4
1 5

예제 출력 1

2

예제 입력 2

2 3
4 5 6
1 2 3

예제 출력 2

0