23104번 - Bunch of Paper 다국어

문제

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$.

제한

힌트