翻译

CP004171.复合逃逸--铂金
NOI/NOI+/CTSC

USACO
通过率：0%

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

输入格式
第一行包含两个空格分隔的整数，
�
N和
�
K (
2
≤
�
≤
30000
,
2
≤
�
≤
6
2≤N≤30000，2≤K≤6).
接下来的每一个
�
N行包含
�
−
1
K−1空格分隔整数：在水平边缘解锁每个门的成本
。
接下来的每一个
�
K行包含
�
−
1
N−1空格分隔整数：在垂直边缘解锁每个门的成本
。
所有费用介于
1
1和
1
0
9
10
9
包容。
在 20% 的测试用例中，可以保证
�
≤
500
N≤500并且所有重量
都在
1
1和
5
5包容。
在另外 20% 的测试用例中，可以保证
�
≤
5000
N≤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 的
大约 1 个门口。有十种选择
不使用成本-10 边缘，所以答案是 <>。