翻译

A787型Compound Escape--铂金
NOI/NOI+/CTSC

USACO
通过率：0%

加入题单
题目描述
贝茜和朋友们被抓获，被困在远离农场的一个秘密大院
里，贝茜要计划他们的逃跑！
该化合物包括
�
�
NK收容单元排列成
�
×
�
N×K
矩形网格，其中水平和垂直
相邻的单元格之间有门。每个牢房只饲养一头奶牛。
贝茜已经入侵了这个系统，并能够解锁
任何门的子集，但每个门都有成本。为了让奶牛逃脱，贝茜必须打开
足够多的大门，让所有的奶牛都可以聚集在一个牢房里（这样它们就有足够的
奶牛力量通过隧道到达地面！Bessie 希望将
总解锁成本降至最低。
但风险比以往任何时候都高，贝茜不能只满足
于一个逃跑计划：她需要后备力量。帮她计算最低成本
逃生计划的数量;如果其中一个计划中需要
解锁某个门，而另一个计划中不需要解锁，则两个计划被认为是不同的。
由于这个数字可能非常大，因此仅输出其剩余模数
1
0
9
+
7
10
9
+7.

输入格式
第一行包含两个空格分隔的整数，
�
N和
�
K (
2
≤
�
≤
30000
,
2
≤
�
≤
6
2≤不≤30000,2≤K≤6).
接下来的每一个
�
N行包含
�
−
1
K−1空格分隔整数：在水平边上解锁每个门的成本
。
接下来的每一个
�
K行包含
�
−
1
N−1空格分隔整数：在垂直边上解锁每个门的成本
。
所有费用介于
1
1和
1
0
9
10
9
包容。
在 20% 的测试用例中，可以保证
�
≤
500
不≤500并且所有权重
都在
1
1和
5
5包容。
在另外 20% 的测试用例中，可以保证
�
≤
5000
不≤5000.

输出格式
单个整数：最小成本逃逸计划的数量，模
1
0
9
+
7
10
9
+7.

输入输出样例
输入#1

复制
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1
输出#1

复制
10
说明/提示
测试用例提供了一个 4x3 网格，
1 1
+-----+-----+
| | |
1 | |2 |1
|5 |6 |
+-----+-----+
| | |
1 | |3 |1
|7 |8 |
+-----+-----+
| | |
1 | |4 |1 | |
|
+-----+-----+
1 1
任何最低成本逃生计划都将使用成本 2 的门口、成本 3 的门口和
成本 1 的大约 9 个门口。有十个选项
不使用成本 1 边缘，所以答案是 10。