SOLVE
LATER
In a \(N\times M\) grid, each grid has a value \(a_{i,j}\). Grid \((i,j)\ (i<N)\) has two extra values \(l_{i,j},r_{i,j}\). The values of each line is not decreasing, that is, for any \(i,j,k(1\le i\le N,1\le j\le k\le M)\), \(a_{i,j}\le a_{i,k}\), and \(l_{i,j}\le l_{i,k},r_{i,j}\le r_{i,k}\) if \(i<N\).
If you are at grid \((i,j)\ (i<N)\), you can go to \((i+1,x)\), where \(x\ge l_{i,j}\) and \(x\le r_{i,j}\). It's guaranteed \(l_{i,j}\le r_{i,j}\) and \(l_{i,j+1}\le r_{i,j}+1\).
Now you walk from some grid \((1,x)\) and end at some grid \((N,y)\), \(x\) and \(y\) are decided by yourself. When you pass a grid \((i,j)\), you add \(a_{i,j}\) to a result array. You need to count hou many different arrays can be obtained. Two arrays are dirrerent if at least one element is different.
First line contains two integers \(N,M(1\le N,M\le 1000)\).
The next \(N\) lines represent a matrix, the \(j\) th integer on the \(i \) th line is \(a_{i,j}\).
Similarily, the next \(N-1\) lines represent \(l\), and the last \(N-1\) lines represent \(r\).
It's guaranteed \(1\le a_{i,j},l_{i,j},r_{i,j}\le M\).
One integer represents the answer, modulo \(10^9+7\).
There are \(6\) different paths, but two of them have the same result array, so the answer is \(5\).
\((1,1)-(2,1)-(3,1):[1,1,1]\)
\((1,1)-(2,1)-(3,2):[1,1,3]\)
\((1,2)-(2,2)-(3,1):[2,1,1]\)
\((1,2)-(2,2)-(3,2):[2,1,3]\)
\((1,3)-(2,3)-(3,2):[2,2,3]\)
\((1,3)-(2,3)-(3,3):[2,2,3]\)