题目描述

在地面上有一个水箱，它的俯视图被划分成了 $n$ 行 $m$ 列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度只能是 $[0,H]$ 之间的整数，请统计有多少可能的水位情况。

因为答案可能很大，请对 $10^9+7$ 取模输出。

我们说两种情况是不同的当且仅当存在至少一个方格的水位在两个情况中不同。

输入格式

第一行包含三个正整数 $n,m,H$。 接下来 $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)$ 之间的墙的高度。

输出格式

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

3 2 2
1
1
1
1 2
1 1

65

提示

对于 $100\%$ 的数据，$n\times m\le500000$，$1\le H\le10^9$。

样例解释：

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