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