题目描述

题目译自 XXV Olimpiada Informatyczna — I etap Powódź

字节城常被暴雨侵袭，这让当地农民头疼不已。他们的方形田地整齐排列成 $m \times n$ 的矩形网格（$m$ 行，每行 $n$ 块，总共 $m n$ 块田）。最让他们苦恼的是，邻田的雨水会溢到自家田里。于是，他们在田间边界建起了各种防洪堤，得意地称之为水坝。每对相邻田地之间有一座高度为 $1$ 到 $H$ 毫米的水坝。网格外边界全被高度为 $H$ 毫米的水坝围住。

你想知道一场大暴雨后，田里的水位会是什么样。为简单起见，只考虑每块田的水位（单位毫米）是 $0$ 到 $H$ 之间的整数。注意，对于每对相邻田地，若它们之间的水坝高度为 $h$ 毫米，两田水位要么相等，要么都不超过 $h$ 毫米。否则，水会从较高的一侧（超过 $h$ 毫米）漫过水坝流到另一侧。

请你写一个程序，计算可能的洪水场景有多少种。两个场景若至少有一块田的水位不同，就视为不同。由于结果可能很大，输出对 $1000000007$ 取模的值。

输入格式

输入的第一行包含三个整数 $m$, $n$, $H$ ($m, n, H \geq 1$)，分别表示矩形网格的行数、列数和最大水位（毫米）。

若 $n > 1$，接下来 $m$ 行，每行 $n-1$ 个整数，表示第 $j$ 行中第 $i$ 块田与第 $i+1$ 块田间水坝的高度。

若 $m > 1$，再接下来 $m-1$ 行，每行 $n$ 个整数，表示第 $i$ 列中第 $j$ 块田与第 $j+1$ 块田间水坝的高度。

输出格式

输出一个整数，表示可能洪水场景的数量，对 $1000000007$ 取模。

样例

输入

3 2 2
1
1
1
1 2
1 1

输出

65

所有田的水位可以全为 $2$（$1$ 种可能），或者每块田独立地取 $0$ 或 $1$（$2^{6} = 64$ 种可能），总共 $65$ 种。

附加样例

• $m=3$, $n=3$, $H=4$；
• $m=1$, $n=1000$, $H=1000$，第 $i$ 个水坝高度为 $i$；
• $m=1000$, $n=500$, $H=1$，所有水坝高度为 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。