翻译

农场的Bessie和她的朋友们被困在一个秘密基地中，远离他们的农场。现在Bessie需要计划他们的逃跑计划！这个基地由一个N×K的矩形网格组成，网格中有NK个囚牛牢房，相邻的牢房之间有门相连。每个牢房中有一头牛。
Bessie已经成功入侵了系统，她可以解锁任意数量的门，但是每个门都有一个解锁的代价。为了让所有的牛能够聚集在一个牢房中（这样他们才能够一起挖地逃到地面上！），Bessie必须打开足够多的门。Bessie希望最小化总的解锁代价。
但是，情况比以往更加严峻，Bessie不能只满足一个逃跑计划，她需要备选方案。帮助她计算最小代价的逃跑计划的数量；如果某个门需要在一个逃跑计划中解锁但在另一个计划中不需要解锁，则认为这两个计划是不同的计划。
由于这个数量可能非常大，只需要输出它除以109+7的余数。
输入格式：
第一行包含两个以空格分隔的整数N和K（2≤N≤30000，2≤K≤6）。
接下来的N行，每行包含K-1个以空格分隔的整数，表示水平边上每个门的解锁代价。
接下来的K行，每行包含N-1个以空格分隔的整数，表示垂直边上每个门的解锁代价。
所有的代价都在1到109之间，包括1和109。
在20%的测试案例中，保证N≤500且所有权值在1到55之间。
在另外20%的测试案例中，保证N≤5000。
输出格式：
一个整数，表示最小代价逃跑计划的数量，除以109+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 1 2 1
| 5 | 6 |
+-----+-----+
| | |
1 1 3 1
| 7 | 8 |
+-----+-----+
| | |
1 1 4 1
| | |
+-----+-----+
最小代价的逃跑计划将使用代价为2的门，代价为3的门，以及一些9个代价为1的门。有10种选择不使用代价为1的门，所以答案是10。