Problem Description

There is a water tank on the ground. Its top view is divided into a grid of $n$ rows and $m$ columns. Between every pair of adjacent cells there is a wall whose thickness can be ignored. Between the tank and the outside world there is a wall of infinite height, so water cannot leak out.

It is known that the water level in each cell can only be an integer in $[0,H]$. Please count how many possible water level configurations there are.

Since the answer may be very large, output it modulo $10^9+7$.

We say two configurations are different if and only if there exists at least one cell whose water level is different in the two configurations.

Input Format

The first line contains three positive integers $n,m,H$.

The next $n$ lines each contain $m-1$ integers $a[i][j](1\le a[i][j]\le H)$, representing the height of the wall between $(i,j)$ and $(i,j+1)$.

The next $n-1$ lines each contain $m$ integers $b[i][j](1\le b[i][j]\le H)$, representing the height of the wall between $(i,j)$ and $(i+1,j)$.

Output Format

Output one line with one integer, the number of configurations modulo $10^9+7$.

3 2 2
1
1
1
1 2
1 1

65

Hint

For $100\%$ of the testdata, $n\times m\le500000$, $1\le H\le10^9$.

Sample Explanation

Either the water level in all cells is $2$, or the water level in all cells is in $[0,1]$. In total, there are $1+2^6=65$ configurations.

Translated by ChatGPT 5