홍수

바이토치아에는 폭우가 자주 내려서, 지역 농부들이 특히 큰 피해를 입는다. 이들의 정사각형 밭은 $m \times n$ 직사각형으로 나란히 놓여 있다(m행, 각 행에 n개, 총 $mn$개). 농부들이 가장 괴로운 경우는 이웃 밭에 내린 빗물이 자기 밭으로 넘쳐 들어올 때다. 그래서 밭 경계마다 장벽을 세우고, 이를 둑이라고 부른다. 인접한 밭 두 개 사이에는 높이가 1밀리미터에서 $H$밀리미터 사이인 둑이 하나씩 있다. 직사각형의 바깥 경계는 모두 높이 $H$밀리미터의 둑으로 막혀 있다.

아주 강한 비가 내린 뒤 밭의 물 높이가 어떻게 될 수 있는지 살펴본다. 단순하게 만들기 위해 각 밭의 물 높이(밀리미터)가 0부터 $H$까지의 정수인 경우만 고려한다. 인접한 두 밭 사이에 높이 $h$밀리미터의 둑이 있으면, 두 밭의 물 높이는 같거나 둘 다 $h$ 이하여야 한다. 그렇지 않으면 높은 쪽 밭의 물($h$밀리미터를 넘는 부분)이 둑을 넘어 다른 밭으로 흐른다.

서로 다른 홍수 시나리오의 개수를 세는 프로그램을 작성하라. 적어도 한 밭의 물 높이가 다르면 두 시나리오는 다른 것으로 본다. 결과가 매우 클 수 있으므로 1000000007로 나눈 나머지를 출력한다.

첫 줄에 직사각형의 크기 $m$, $n$과 밀리미터 단위의 최대 물 높이 $H$ ($m, n, H \ge 1$)가 정수 세 개로 주어진다.

$n > 1$이면, 다음 $m$줄에 각각 $n-1$개의 정수가 주어진다. $j$번째 줄의 $i$번째 수는 $j$행에 있는 밭 $i$와 밭 $i+1$ 사이 둑의 높이다.

$m > 1$이면, 이어서 $m-1$줄에 각각 $n$개의 정수가 주어진다. $j$번째 줄의 $i$번째 수는 $i$열에 있는 밭 $j$와 밭 $j+1$ 사이 둑의 높이다.

가능한 홍수 시나리오의 개수를 1000000007로 나눈 나머지를 정수 하나로 출력한다.

$mn \le 500000$

$H \le 10^9$

아래 입력에서는 모든 밭의 물 높이가 2인 경우(1가지)가 있다. 또한 6개의 밭이 각각 독립적으로 물 높이 0 또는 1을 가질 수 있다($2^6 = 64$가지).