Description

在地面上有一个水箱，它的俯视图被划分成了 $n$ 行 $m$ 列个方格，

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

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

Input Format

第一行包含三个正整数 $n,m,H$（$n\times m\le 5 \times 10^5,1\le H\le10^9$）。

接下来 $n$ 行，每行 $m-1$ 个整数 $a_{i,j}$（$1\le a_{i,j}\le H$），表示 $(i,j)$ 和 $(i,j+1)$ 之间的墙的高度。

接下来 $n-1$ 行，每行 $m$ 个整数 $b_{i,j}$（$1\le b_{i,j}\le H$），表示 $(i,j)$ 和 $(i+1,j)$ 之间的墙的高度。

Output Format

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

Sample

3 2 2
1
1
1
1 2
1 1

65

HINT

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

Source

鸣谢Claris上传试题