Grid Walk
Tag(s):

Algorithms, DP, Medium, String

Problem
Editorial
Analytics

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.

Input format

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$.

Output format

One integer represents the answer, modulo $10^9+7$.

SAMPLE INPUT
3 3
1 2 2
1 1 2
1 3 3
1 2 3
1 1 2
1 2 3
2 2 3

SAMPLE OUTPUT
5

Explanation

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]$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor Challenge Name

September Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Sorting
• Math > Convex Hull
• Basic Programming > Recursion
• Data Structures > Trees