[USACO19OPEN]Compound Escape P

题目描述

Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋,现在该是Bessie站出来策划脱逃的时候了!这一房屋包含 $ NK $ 个排列成 $ N \times K $ 矩形方阵的囚室,水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。 Bessie黑进了系统,可以解锁任意一部分的门,但是每个门均有其代价。为了使奶牛们能够脱逃,Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内(这样她们就能拥有足够的力量挖地洞通向外面!)。Bessie想要使得总的解锁花费最小。 但是这次行动异常关键,Bessie不能满足于仅仅一个脱逃方案:她还需要后备方案。帮助她计算最小代价脱逃方案的数量;如果某一扇门在一个方案中被解锁了而在另一个方案中没有,那么这两个方案就被认为是不同的。 由于这个数字可能非常大,只需输出该数对 $ 10^9+7 $ 取模后的结果。

输入输出格式

输入格式


输入的第一行包含两个空格分隔的整数 $ N $ 和 $ K $ ( $ 2 \leq N \leq 30000 ,2 \leq K \leq 6 $ )。 以下 $ N $ 行每行包含 $ K-1 $ 个空格分隔的整数,为解锁一条水平边上的每扇门需要花费的代价。 以下 $ K $ 行每行包含 $ N-1 $ 个空格分隔的整数,为解锁一条垂直边上的每扇门需要花费的代价。 所有的花费均在 $ 1 $ 到 $ 10^9 $ 之间。

输出格式


一个整数:最小花费的逃脱方案的数量,对 $ 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。 ### 子任务 对于20%的测试数据,保证 $ N \leq 500 $ ,所有的代价均在 $ 1 $ 到 $ 5 $ 之间。 对于另外20%的测试数据,保证 $ N \leq 5000 $ 。