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

## This Problem was Asked in

Challenge Name

September Circuits '18

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