Byteotia 经常遭受暴雨袭击，这对当地农民来说是灾难性的。他们的单位正方形田地整齐地排列在一个 $m \times n$ 的矩形中（共有 $m$ 行 $n$ 列，总计 $mn$ 块田地）。为了防止水从相邻的田地溢出到自己的田地中，农民们在田地的边缘建造了各种各样的屏障，他们自豪地称之为“水坝”。在每对相邻的田地之间，都有一个高度在 $1$ 到 $H$ 毫米之间的水坝。我们假设大矩形的所有外边缘都有高度为 $H$ 毫米的水坝。

我们对大雨后田地中可能的水位感兴趣。为简化起见，我们只考虑每块田地的水位（以毫米为单位）均为 $0$ 到 $H$ 之间的整数的情况。请注意，对于每一对相邻的田地，如果它们之间的水坝高度为 $h$，那么这两块田地的水位要么相等，要么都不超过 $h$ 毫米。否则，水会从水位较高（超过 $h$ 毫米）的田地溢出到另一块田地。

编写一个程序，确定有多少种不同的洪水情景。如果两个情景中至少有一块田地的水位不同，我们就认为它们是不同的。由于结果可能非常大，请输出其对 $1\,000\,000\,007$ 取模的结果。

输入格式

标准输入的第一行包含三个整数 $m, n, H$ ($m, n, H \ge 1$)，分别指定了外矩形的尺寸和最大水位（以毫米为单位）。

如果 $n > 1$，接下来的 $m$ 行，每行包含 $n - 1$ 个整数。其中第 $j$ 行的第 $i$ 个数指定了第 $j$ 行中从左往右数第 $i$ 块田地与第 $i+1$ 块田地之间的水坝高度。

如果 $m > 1$，接下来的 $m - 1$ 行，每行包含 $n$ 个整数。其中第 $i$ 行的第 $j$ 个数指定了第 $i$ 列中从上往下数第 $j$ 块田地与第 $j+1$ 块田地之间的水坝高度。

输出格式

输出一个整数，表示可能的洪水情景数量对 $1\,000\,000\,007$ 取模的结果。

样例

样例输入 1

3 2 2
1
1
1
1 2
1 1

样例输出 1

65

说明

样例说明：所有田地的水位可以均为 $2$（$1$ 种情景），或者每块田地的水位可以独立地为 $0$ 或 $1$（$2^6 = 64$ 种情景）。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试点。