Problem Description

There are $ N $ papers numbered from $ 1 $ to $ N $, each containing $ K $ integers.

The integers written on the $ i $ th paper are $v_{i,1},\ v_{i,2},\ \ldots\ v_{i,K}$.

Consider creating a sequence by independently selecting one integer from each paper such that the integer chosen from the $ i $ th paper is the $ i $ th term of the sequence.

There are $ K^N $ ways to create such sequences, but how many of them are non-decreasing? Since the answer can be very large, output it modulo $ 10^9+7 $.

A sequence $A=(a_1,\ a_2,\ \ldots\ ,\ a_N)$ is non-decreasing if for all $i\ (1\ \leq\ i\ \leq\ N-1)$, $a_i\ \leq\ a_{i+1}$ holds.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ v_{1,1} $ $ v_{1,2} $ $\cdots$ $ v_{1,K} $ $ v_{2,1} $ $ v_{2,2} $ $\cdots$ $ v_{2,K} $ $\vdots$ $ v_{N,1} $ $ v_{N,2} $ $\cdots$ $ v_{N,K} $

Output Format

Output the number of non-decreasing sequences as described in the problem statement, modulo $ 10^9+7 $, in one line.

Sample Input and Output

Sample Input #1

2 2
2 4
1 5

Sample Output #1

2

Sample Input #2

2 3
4 5 6
1 2 3

Sample Output #2

0

Sample Input #3

20 20
2 8 12 17 19 29 41 53 57 62 63 65 67 70 71 74 76 77 96 100
2 3 9 13 15 16 20 26 28 33 38 39 46 51 58 59 74 92 93 99
2 5 6 9 19 20 22 24 26 35 41 45 56 60 62 74 76 81 83 96
3 7 10 11 13 15 17 20 22 26 34 35 43 59 68 78 82 83 85 93
1 7 11 14 17 26 37 41 45 49 62 63 64 67 71 74 88 89 91 94
12 15 17 19 22 24 28 29 31 46 50 51 55 59 64 65 74 79 91 95
7 11 17 22 23 27 29 33 37 39 45 50 51 52 62 67 69 71 85 90
9 11 12 18 22 30 40 41 43 49 51 59 62 71 74 94 95 96 99 100
15 17 21 23 24 28 33 39 44 45 48 52 54 59 72 76 88 89 99 100
1 6 12 13 14 21 25 37 48 49 56 57 71 72 77 79 83 85 93 98
10 20 22 25 34 45 49 52 58 60 62 67 69 74 75 77 81 84 96 97
6 7 23 36 41 43 45 46 50 51 52 57 58 61 73 74 85 87 94 97
4 20 26 36 37 41 44 45 47 51 56 57 72 73 74 79 86 91 97 98
8 10 17 24 25 29 31 32 34 46 53 57 60 71 74 78 79 80 90 91
12 15 16 17 27 32 33 35 41 51 55 56 58 67 69 71 74 89 90 91
4 13 17 24 25 27 39 40 43 48 51 54 61 62 63 68 72 76 87 90
8 10 12 18 22 37 40 43 46 50 51 58 59 65 74 85 86 89 96 98
1 9 16 17 19 34 37 50 54 55 57 58 59 69 72 76 77 84 92 99
3 10 11 12 13 17 24 28 36 39 45 49 50 58 74 78 79 80 84 93
5 15 16 20 22 24 29 41 44 55 56 60 62 63 68 73 85 86 93 100

Sample Output #3

188926982

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ K\ \leq\ 10000$
• $1\ \leq\ v_{i,1}\ <\ v_{i,2}\ <\ \cdots\ <\ v_{i,K}\ \leq\ 10^9\ (1\ \le\ i\ \le\ N)$
• All inputs are integers.

Sample Explanation 1

The possible sequences are:
- $ (2,1) $
- $ (2,5) $
- $ (4,1) $
- $ (4,5) $

Among these, the non-decreasing sequences are $ (2,5) $ and $ (4,5) $, so the answer is $ 2 $.

Sample Explanation 2

There are cases where it is impossible to choose integers to form a non-decreasing sequence.

Sample Explanation 3

Be careful to output the answer modulo $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分