翻译（非机翻）

题目描述
Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是Bessie站出来策划脱逃的时候了！这一房屋包含
�
�
NK 个排列成
�
×
�
N×K 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。

Bessie黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie想要使得总的解锁花费最小。

但是这次行动异常关键，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
之间。

输出格式
一个整数：最小花费的逃脱方案的数量，对
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