Diamond Rush

Problem Description

There are $n \times n$ cells 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 $\left(n^2\right)^{a_{i,j}}$ diamonds. 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-2$ moves. 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 $q$ queries. 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\leq i\leq xr$ and $yl\leq j\leq yr$.

Input

The first line of the input contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases. For each case, the first line of the input contains two integers $n$ and $q$ ($2 \leq n \leq 400,1\leq q\leq 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 $a_{i,1},a_{i,2},\dots,a_{i,n}$ ($1\leq a_{i,j}\leq n^2$), denoting the number of diamonds in each cell. Each of the following $q$ lines contains four integers $xl,xr,yl$ and $yr$ ($1\leq xl\leq xr\leq n,1\leq yl\leq yr\leq n$), denoting each query. It is guaranteed that you can find at least one valid path in each query.

Output

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 $10^9+7$ instead.

Sample Input

1
2 2
2 3
1 4
1 1 2 2
2 2 1 1

Sample Output

276
336

Source

2020 Multi-University Training Contest 2