Bunch of Paper

Time limit2sMemory limit512 MB

Summary

Count non-decreasing sequences that pick one value from each of N sorted lists of K integers, modulo 1e9+7.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Binary search, Combinatorics
Solved: No attempts yet

Problem

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

Choose one integer from each sheet to form the sequence $a_i$ , where the integer chosen from the $i$ -th sheet becomes $a_i$ . There are $K^N$ ways to form such a sequence. How many of them are non-decreasing? A sequence is non-decreasing if $a_i \le a_{i+1}$ for every $1 \le i \le N-1$ .

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

Input

The first line 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$ ).

Output

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

Examples2

Example 1
Input
```
2 2
2 4
1 5
```
Expected output
```
2
```
Example 2
Input
```
2 3
4 5 6
1 2 3
```
Expected output
```
0
```