종이 뭉치

정수 $1$부터 $N$까지의 번호가 붙은 종이가 $N$장 있다. 종이마다 $K$개의 정수가 적혀 있어, $i$번째 종이에는 $v_{i,1}, v_{i,2}, \ldots, v_{i,K}$가 적혀 있다.

각 종이에서 정수를 하나씩 골라 수열 $a_i$를 만든다. $i$번째 종이에서 고른 정수가 $a_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}, \ldots, v_{i,K}$가 주어진다. ($1 \le v_{i,1} < v_{i,2} < \ldots < v_{i,K} \le 10^9$)

감소하지 않는 수열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.