#P5101. [POI2018]Powódź

    ID: 4187 传统题 1000ms 512MiB 尝试: 333 已通过: 142 难度: 7 上传者: 标签>CF2200提高+/省选-Kruskal普通并查集计数 DP乘法原理鸣谢Claris上传试题

[POI2018]Powódź

Description

在地面上有一个水箱,它的俯视图被划分成了 nn 行 mm 列个方格,

相邻两个方格之间有一堵厚度可以忽略不计的墙,水箱与外界之间有一堵高度无穷大的墙,因此水不可能漏到外面。

已知水箱内每个格子的高度都是 [0,H][0,H] 之间的整数,请统计有多少可能的水位情况。因为答案可能很大,请对 109+710^9+7 取模输出。两个情况不同当且仅当存在至少一个方格的水位在两个情况中不同。

Input Format

第一行包含三个正整数 n,m,Hn,m,H(n×m≤5×105,1≤H≤109n\times m\le 5 \times 10^5,1\le H\le10^9)。

接下来 nn 行,每行 m−1m-1 个整数 ai,ja_{i,j}(1≤ai,j≤H1\le a_{i,j}\le H),表示 (i,j)(i,j) 和 (i,j+1)(i,j+1) 之间的墙的高度。

接下来 n−1n-1 行,每行 mm 个整数 bi,jb_{i,j}(1≤bi,j≤H1\le b_{i,j}\le H),表示 (i,j)(i,j) 和 (i+1,j)(i+1,j) 之间的墙的高度。

Output Format

输出一行一个整数,即方案数模 109+710^9+7 的结果。

Sample

3 2 2
1
1
1
1 2
1 1
65

HINT

要么全部格子水位都是 22,要么全部格子水位都在 [0,1][0,1] 之间,共 1+26=651+2^6=65 种情况。

Source

鸣谢Claris上传试题