← 返回题目列表

AtCoder · kupc2020_b

B. 纸上的数字

中文机器翻译题面 查看原题

配点 : 200 点

問題文

1 从 N 的 N 张纸,每张纸上分别写有 K 个整数。第

i 张纸上写的整数是 v_{i,1}, v_{i,2}, \ldots v_{i,K} 。

从每张纸独立地选择 1 个整数,第i 张纸选出的整数成为数列的项目, i 考虑构造这样的数列的方式。

这种数列的构造方法是K^N有多少种情况,其中广义单调递增的有多少种呢?由于答案可能非常大,10^9+7 的余数。

但是,数列 A=(a_1, a_2, \ldots , a_N) 被称为广义单调递增,是指对于所有 i (1 \leq i \leq N-1) 反对 a_i \leq a_{i+1} 都成立。

制約

  • 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)
  • 输入全部为整数。

入力

输入是按以下格式从标准输入给出的。

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}

出力

在问题中提到的数列中,有多少是广义单调递增的,10^9+7 输出除以 后的余数,一行显示。


入力例 1

2 2
2 4
1 5

出力例 1

2

可能的数列如下 4 个。

  • (2,1)
  • (2,5)
  • (4,1)
  • (4,5)

其中广义单调递增的有 (2,5) 和 (4,5) ,因此答案是 2 。


入力例 2

2 3
4 5 6
1 2 3

出力例 2

0

无论如何选择整数,都存在无法使其成为广义单调递增的情况。


入力例 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

出力例 3

188926982

10^9+7 请注意输出除以该数的余数。