시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB63350.000%

문제

There are $N$ sheets of paper, enumerated by sequential integers from $1$ to $N$. Each sheet has $K$ integers written on it, so $i$-th sheet contains the integers $v_{i,1}, v_{i,2}, \ldots, v_{i,K}$.

Then we choose one integer from each sheet and create the sequence $a_i$, where $i$-th integer is chosen from $i$-th sheet of paper. There are $K^N$ ways to make such a sequence. How many of them are non-decreasing? A sequence is non-decreasing if $a_i \le a_{i+1}$ for all $1 \le i \le N-1$.

The answer may be too large, so print it modulo $10^9 + 7$.

입력

The first line of the input contains two integers $N$ and $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$). The $i$-th of the following $N$ lines contains $K$ integers $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$).

출력

Print the number of non-decreasing sequences, modulo $10^9 + 7$.

예제 입력 1

2 2
2 4
1 5

예제 출력 1

2

예제 입력 2

2 3
4 5 6
1 2 3

예제 출력 2

0