7449: Diamond Rush

There are n×ncells on a grid, the top-left cell is at (1,1)while the bottom-right cell is at (n,n). In the cell at (i,j), there are (n2)ai,jdiamonds.
Initially, you are at (1,1), every time you can move to (i+1,j)or (i,j+1)from (i,j)without moving out of the grid. Your destination is at (n,n), so you will take exactly 2n−2moves. When you are at a cell, you can take all the diamonds inside this cell, including the starting point (1,1)and the destination (n,n).
However, some cells are blocked but you don't know which cells are blocked. Please write a program to answer qqueries. In each query, you will be given four integers xl,xr,yl,yr, you need to report the maximum number of diamonds that you can take without passing the cells (i,j)such that xl≤i≤xrand yl≤j≤yr.

The fifirst line of the input contains a single integer T (1 ≤ T ≤ 5), the number of test cases.

For each case, the fifirst line of the input contains two integers n and q (2 ≤ n ≤ 400, 1 ≤ q ≤ 200 000),

denoting the size of the grid and the number of queries.

Each of the following n lines contains n integers, the i-th line contains ai,1, ai,2, . . . , ai,n (1 ≤ ai,j ≤ n2 ),

denoting the number of diamonds in each cell.

Each of the following q lines contains four integers xl, xr, yl and yr (1 ≤ xl ≤ xr ≤ n, 1 ≤ yl ≤ yr ≤ n),

denoting each query. It is guaranteed that you can fifind at least one valid path in each query.

For each query, print a single line containing an integer, denoting the maximum number of diamonds that

you can take. Note that the answer may be extremely large, so please print it modulo 109 + 7 instead.