다이아몬드 러시

$n \times n$ 크기의 격자가 있다. 가장 왼쪽 위 칸은 $(1,1)$, 가장 오른쪽 아래 칸은 $(n,n)$이다. $i$행 $j$열의 칸 $(i,j)$에는 $\left(n^2\right)^{a_{i,j}}$개의 다이아몬드가 있다.

$(1,1)$에서 출발해 $(n,n)$까지 이동한다. 칸 $(i,j)$에서는 격자를 벗어나지 않는 범위에서 $(i+1,j)$ 또는 $(i,j+1)$로 이동할 수 있다. 이동은 정확히 $2n-2$번 한다. 칸에 도착하면 그 칸의 다이아몬드를 모두 가져갈 수 있다. 시작점 $(1,1)$과 도착점 $(n,n)$의 다이아몬드도 포함된다.

일부 칸은 막혀 있지만 어느 칸이 막혀 있는지는 알 수 없다. 각 질의는 $r_1 \le i \le r_2$, $c_1 \le j \le c_2$를 만족하는 칸들의 직사각형을 준다. 경로는 이 직사각형에 속한 칸을 하나도 지나지 않아야 한다. 가져갈 수 있는 다이아몬드의 최댓값을 구하라. 각 질의마다 유효한 경로가 적어도 하나 존재함이 보장된다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 5$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 $n$과 $q$ ($2 \le n \le 400$, $1 \le q \le 200\,000$)가 주어진다. 이후 $n$개의 줄에 걸쳐 $i$번째 줄에 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n^2$)이 주어진다. 이후 $q$개의 줄에 질의 $r_1, r_2, c_1, c_2$ ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le n$)가 주어진다.

각 질의에 대해 가져갈 수 있는 다이아몬드의 최댓값을 한 줄에 출력한다. 값이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.