스키 코스

산악 지형이 $N$행 $M$열의 격자로 주어진다. 격자의 각 칸에는 그 지점의 지형 높이가 적혀 있다. 스키어를 위해 선택된 여러 지점 쌍 사이에 $K$개의 스키 리프트가 설치되어 있다. 모든 리프트는 한 방향으로만 동작하여, 낮은 지점에서 더 높은 지점으로 스키어를 올려 준다.

스키 코스는 다음과 같이 이루어진다. 먼저 리프트 탑승을 한 번 이상 연속으로 하며(이 동안 스키어의 높이는 계속 높아진다), 그다음 출발한 지점으로 돌아오는 활강을 한다. 연이은 리프트 탑승은 서로 이어져야 한다. 즉 각 탑승은 바로 앞 탑승이 끝난 지점에서 시작한다. 각 활강은 상하좌우 네 방향 중 한 방향으로 인접한 칸으로 한 칸 이동하는 것이며, 모든 활강은 더 높은 칸에서 더 낮은 칸으로만 갈 수 있다.

스키장은 "우리에게는 $X$개의 스키 코스가 있습니다"라는 문구로 홍보하려 한다. 리프트 목록과 각 지점의 높이가 주어질 때, $X$를 $10^9 + 7$로 나눈 나머지를 구하여라.

첫째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 공백으로 구분된 두 정수 $N$, $M$ ($1 \le N, M \le 100$)이 주어진다. 다음 $N$개의 줄은 높이 표를 $1$행부터 $N$행까지 차례로 나타내며, 각 줄에는 $M$개의 정수 $h$ ($0 \le h \le 10^9$)가 $1$열부터 $M$열까지 순서대로 주어진다.

그다음 줄에는 리프트의 수 $K$ ($1 \le K \le 300$)가 주어진다. 이어지는 $K$개의 줄에는 각각 네 정수 $w_0\ c_0\ w_1\ c_1$이 주어지며, 이는 지점 $(w_0, c_0)$에서 지점 $(w_1, c_1)$로 가는 리프트가 있음을 뜻한다. 행 번호는 $1$부터 $N$까지, 열 번호는 $1$부터 $M$까지이다. 모든 리프트의 도착 지점은 출발 지점보다 높이가 반드시 더 높다. 같은 두 지점을 잇는 리프트가 여러 개 있을 수도 있다.

각 테스트 케이스마다 스키 코스의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

여기서 $(r, c)$는 $r$행 $c$열의 칸을 뜻한다.

첫 번째 예제에서 가능한 코스는 다음과 같다.

• $(1,1) \to (1,2) \to (1,1)$
• $(1,1) \to (1,2) \to (2,2) \to (1,2) \to (1,1)$
• $(1,1) \to (1,2) \to (2,2) \to (2,1) \to (1,1)$
• $(1,1) \to (2,1) \to (1,1)$
• $(1,2) \to (2,2) \to (1,2)$

두 번째 예제는 같은 두 지점을 잇는 리프트가 여러 개 있을 수 있음을 보여 준다.