시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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 $(i,j)$ which is at row $i$ and column $j$, there are $\left(n^2\right)^{a_{i,j}}$ diamonds.

You start at $(1,1)$ and move to $(n,n)$. At any cell $(i,j)$, you can move to $(i+1,j)$ or $(i,j+1)$, provided that you don't move out of the grid. Clearly, you will make exactly $2n-2$ steps. When you are at a cell, you can take all the diamonds at 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 $r_1$, $r_2$, $c_1$, $c_2$, and you need to report the maximum number of diamonds that you can take without passing the cells $(i,j)$ such that $r_1 \leq i \leq r_2$ and $c_1 \leq j \leq c_2$.

입력

The first line contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases. For each test case:

The first line 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 $r_1$, $r_2$, $c_1$, $c_2$ ($1 \leq r_1 \leq r_2 \leq n$, $1 \leq c_1 \leq c_2 \leq n$) describing a query. It is guaranteed that you can find at least one valid path in each query.

출력

For each query, print a single line containing an integer: 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.

예제 입력 1

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

예제 출력 1

276
336