Logan and his MATRIX game

All submissions for this problem are available.
Charles: "She can learn to be BETTER."
Logan: "Better than me??"
Charles: "Actually, YES!!"
Charles wants Logan to train Laura, and Logan reluctantly agrees.
As a part of the training, Logan and Laura visit a park which is in the form of a rectangular grid i.e like a Matrix
The rows are defined in top to bottom order, and the columns are defined in left to right order
At each of the position represented as , there exists an item of value
.Logan decided to train Laura by giving her difficult tasks.
Each of the tasks can be defined as follows:
Logan provides Laura coordinates of 2 rectangular subgrids.
First of all, Laura must ignore the common area of both the rectangular subgrids.
Now, with the area remaining in both subgrids, she has to find
Logan doesn't stop at this, as he wants Laura to be the best.
He takes Laura to another park in the form of a square grid i.e like a matrix
If Laura is at some point in the grid , then in a single step she can move to another point if the following condition is satisfied:
Now, he gives her queries to answer.
In each query, Logan provides her a coordinate inside the grid
She has to move exactly steps in the square grid.
The steps must be taken in such a way that at each instant she stays in the park only.
Laura needs to tell the distinct number of ways to achieve the required goal.
Two ways are considered to be different if they have atleast one different step.
As the number of ways can be very large, print the answer modulo 10^{9}+7
Note: Large I/O Files. Use Fast I/O like scanf/printf for C++
Input
First line contains 2 integers  R and C denoting the dimensions of the matrix M
R lines follow, with each line comprising C integers.
Next line contains integer K denoting the number of tasks to be performed .
K lines follow.
Each of the K lines has 8 integers R1, C1, R2, C2, R3, C3, R4, C4  such that first four integers are coordinates of first rectangular subgrid. (R1,C1 ) denotes the top left corner, and (R2,C2) denotes the bottom right corner of the rectangular subgrid 1. and next four integers are coordinates of second rectangular subgrid. (R3,C3 ) denotes the top left corner, and (R4,C4) denotes the bottom right corner of the rectangular subgrid 2.
Next line contains integer T  dimension of square matrix N
Next line contains integer Z the number of queries to be answered.
Z lines follow.
Each of the next Z lines has 2 integers  A and B denoting the starting coordinate
Output
For each of the Z queries, print the required number of ways as described. For each query, answer must be on the separate line.
Constraints
 1 ≤ R,C ≤ 1000
 1 ≤ M(i,j) ≤ 10^{9}
 1 ≤ K ≤ 20000
 1 ≤ R1 ≤ R2 ≤ R
 1 ≤ R3 ≤ R4 ≤ R
 1 ≤ C1 ≤ C2 ≤ C
 1 ≤ C3 ≤ C4 ≤ C
 Both the rectangular subgrids are not exactly same
 1 ≤ T ≤ 20
 1 ≤ Z ≤ 400
 1 ≤ A,B ≤ T
Example
3 3
1 1 3
1 6 1
8 1 1
1
1 1 2 2 2 2 3 3
3
1
1 1
Output:64
Explanation
The rectangular grid can be shown as above.
Blue colored region denotes first subgrid, and red colored region denotes second subgrid
After eliminating the overlapping region, we see than Min=1 and Max=1
So, Y=2
In the square grid of size 3, starting point is (1,1)
There are 64 different ways in which Laura can move 2 steps from cell (1,1).
Author:  shivamg_isc 
Tags  shivamg_isc 
Date Added:  23032017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions