Problem 2. Compound Escape

USACO 2019 US Open Contest, Platinum

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

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

但是这次行动异常关键，Bessie不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。

由于这个数字可能非常大，只需输出该数对$10^9 + 7$取模的余数。

输入格式（文件名：escape.in）：

输入的第一行包含两个空格分隔的整数$N$和$K$（$2 \le N \le 30000, 2 \le K \le 6$）。

以下$N$行每行包含$K-1$个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。

以下$K$行每行包含$N-1$个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。

所有的花费均在$1$到$10^9$之间。

对于20%的测试数据，保证$N \leq 500$，所有的代价均在$1$到$5$之间。

对于另外20%的测试数据，保证$N \leq 5000$。

输出格式（文件名：escape.out）：

一个整数：最小花费的逃脱方案的数量，对$10^{9} + 7$取模。

输入样例：

4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
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。

供题：Brian Dean