Description

在地面上有一个水箱，它的俯视图被划分成了n行m列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水 箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度都是[0,H]之间的整数 ，请统计有多少可能的水位情况。因为答案可能很大，请对10^9+7取模输出。两个情况不同当且仅当存在至少一个 方格的水位在两个情况中不同。

Input

第一行包含三个正整数n,m,H(n*m<=500000,1<=H<=10^9)。 接下来n行，每行m-1个整数a[i]j，表示(i,j)和(i,j+1)之间的墙的高度。 接下来n-1行，每行m个整数b[i]j，表示(i,j)和(i+1,j)之间的墙的高度。

Output

输出一行一个整数，即方案数模10^9+7的结果。

Sample Input

3 2 2

1

1

1

1 2

1 1

Sample Output

65

HINT

先吐槽一波，你边界围墙高度既然是无穷大，那么也就是说我填多少水都可以咯，那方案数不应该是无穷大吗，enmmm 考虑把每堵墙看做一条边，不难发现只有最小生成树上的边是有用的。 那么我们考虑在Kruskal算法的加边过程中顺便统计答案。 对于当前每一个连通块x，设mx[x]表示x中的最大边权，s[x]表示在连通块x中每个点的点权不超过mx[x]时的方案数。 当合并两个连通块x和y时，设当前边权为w，那么显然有s[x+y]=(s[x]+w-mx[x])*(s[y]+w-mx[y])。 就做完了。

CODE

#include <bits/stdc++.h> typedef long long ll; const int N = 500005; const int MOD = 1000000007; int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f; } struct Edge { int x,y,w; }e[N * 2]; int cnt; int n,m,h; int point(int x,int y) { return (x - 1) * m + y; } bool cmp(Edge a,Edge b) { return a.w < b.w; } int f[N],s[N],mx[N]; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { n = read(), m = read(), h = read(); for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) e[++cnt].x = point(i,j), e[cnt].y = point(i, j + 1), e[cnt].w = read(); for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) e[++cnt].x = point(i, j), e[cnt].y = point(i + 1, j), e[cnt].w = read(); for (int i = 1; i <= n * m; i++) f[i] = i, s[i] = 1, mx[i] = 0; std::sort(e + 1, e + cnt + 1, cmp); for (int i = 1; i <= cnt; i++) { int x = find(e[i].x), y = find(e[i].y), w = e[i].w; if (x == y) continue; s[y] = 1ll * (s[x] + w - mx[x]) * (s[y] + w - mx[y]) % MOD; f[x] = y, mx[y] = w; } printf("%d\n",(s[find(1)] + h - mx[find(1)]) % MOD); }