집 사기

집을 사려고 부동산 회사에 연락했습니다. 이 회사는 막 사업을 시작했고, 당신은 이 회사의 첫 번째 고객입니다. 그래서 회사는 당신에게 특별한 제안을 합니다.

회사는 너비 $W$, 높이 $H$인 직사각형 모양의 땅 한 필지를 가지고 있습니다. 위치는 왼쪽 아래 모서리를 원점 $(0, 0)$으로 하는 좌표계로 나타냅니다. 이 모서리에서 오른쪽으로 $x$, 위쪽으로 $y$만큼 떨어진 점을 $(x, y)$로 쓰며, 땅 위의 모든 점은 $0 \le x \le W$, $0 \le y \le H$를 만족합니다.

이 땅에는 이미 여러 채의 집이 지어져 있습니다. 각 집은 변이 땅의 변과 평행한 축 정렬 직사각형이며, 어떤 두 집도 서로 겹치지 않습니다. 하나의 집은 네 정수 $x_1, y_1, x_2, y_2$로 주어지는데, $(x_1, y_1)$은 집의 왼쪽 아래 모서리, $(x_2, y_2)$는 오른쪽 위 모서리입니다.

특별한 제안은 다음과 같습니다. 당신은 땅에서 정확히 한 채의 집을 포함하는 축 정렬 직사각형 영역을 고를 수 있으며, 그 집 주변의 빈 공간을 원하는 만큼 함께 가질 수 있습니다. 집이 차지한 땅만 원한다면 딱 그만큼만 골라도 되고, 여유가 있다면 집 주변에 정원 같은 빈 공간을 남겨 둘 수도 있습니다.

고르는 영역은 다음 규칙을 지켜야 합니다.

• 영역의 변은 땅의 변과 평행해야 하고, 네 모서리는 모두 정수 좌표여야 합니다. 예를 들어 $(3, 2)$는 되지만 $(3.5, 2)$는 안 됩니다.
• 어떤 집도 영역의 경계로 잘려서는 안 됩니다. 즉 모든 집은 영역 안에 완전히 들어오거나, 영역 밖에 완전히 나가 있어야 합니다.
• 영역은 정확히 한 채의 집만 포함해야 합니다. 집이 하나도 없거나 두 채 이상 있으면 안 됩니다.

이런 영역을 고르는 방법은 몇 가지입니까?

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $T$(약 $500$)가 주어집니다.

각 테스트 케이스의 첫째 줄에는 땅의 너비와 높이를 나타내는 두 정수 $W$와 $H$($1 \le W, H \le 10^9$)가 주어집니다. 다음 줄에는 집의 수를 나타내는 정수 $N$($1 \le N \le 50$)이 주어집니다. 이어지는 $N$개의 줄에는 각 집을 나타내는 네 정수 $x_1\ y_1\ x_2\ y_2$($0 \le x_1 < x_2 \le W$, $0 \le y_1 < y_2 \le H$)가 주어집니다. 어떤 두 집도 겹치지 않으며, 모든 좌표는 음이 아닌 정수입니다.

각 테스트 케이스마다 Case k: A 형식으로 한 줄을 출력합니다. 여기서 k는 테스트 케이스 번호($1$부터 시작)이고, A는 고를 수 있는 영역의 수입니다. 이 수가 매우 커질 수 있으므로 $10^9 + 7$으로 나눈 나머지를 출력합니다.