너의 길

여러분은 잘 계획된 작은 직사각형 마을에 삽니다. 마을 중심부의 크기는 세로 $H$ 킬로미터, 가로 $W$ 킬로미터이며, 각각 크기가 $1 \times 1\ \text{km}^2$인 $H \times W$개의 단위 블록으로 나뉩니다. 서쪽에서 동쪽으로 뻗은 도로가 $H + 1$개, 북쪽에서 남쪽으로 뻗은 대로가 $W + 1$개 있어서, 중심부는 아래 그림처럼 평면 위의 직사각형으로 볼 수 있습니다.

그림 1. $H = 3$, $W = 6$인 마을의 중심부.

각 교차점은 평면 좌표로 나타냅니다. 위 그림에서 왼쪽 아래 모서리는 교차점 $(0, 0)$이고 오른쪽 위 모서리는 교차점 $(6, 3)$입니다.

여러분의 집은 왼쪽 아래 모서리 $(0, 0)$에 있고, 오른쪽 위 모서리 $(W, H)$에 있는 대학교로 가려고 합니다. 헛수고를 하지 않기 위해, 항상 서쪽에서 동쪽으로, 또는 남쪽에서 북쪽으로만 걷습니다. 이렇게 걸으면 위 예시에서 대학교에 이르는 경로는 $84$가지입니다.

여러분은 $K$일 동안 대학교에 갑니다. 매일 아침 도시가 청소를 위해 도로와 대로의 일부를 막으면서 일이 복잡해집니다. 막힌 구간들은 항상, 서쪽에서 동쪽 그리고 남쪽에서 북쪽으로만 걷는 어떤 경로로도 한 막힌 구간에서 다른 막힌 구간에 도달할 수 없도록 배치됩니다. 즉, 하나의 단조 경로가 두 개의 막힌 구간을 동시에 지날 수는 없습니다.

여러분은 여전히 서쪽에서 동쪽, 남쪽에서 북쪽으로만 이동합니다. 각 날에 대해 대학교에 이르는 경로가 몇 가지인지 구하세요. 그 수가 매우 커질 수 있으므로, $2552$로 나눈 나머지를 출력합니다.

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어집니다 ($1 \le T \le 5$). 각 테스트 케이스는 다음 형식을 따릅니다.

각 테스트 케이스의 첫 줄에는 세 정수 $W$, $H$, $K$가 주어집니다 ($1 \le W \le 1000$; $1 \le H \le 1000$; $1 \le K \le 10000$). $W$와 $H$는 중심부의 크기를, $K$는 대학교에 가는 날 수를 나타냅니다.

이어지는 $K$개의 줄은 하루씩의 막힌 구간 정보를 나타냅니다. $i$번째 줄($1 \le i \le K$)은 막힌 구간의 개수를 나타내는 정수 $Q_i$($1 \le Q_i \le 100$)로 시작하고, 그 뒤에 네 정수로 이루어진 묶음이 $Q_i$개 따라옵니다. 각 묶음 $A$, $B$, $C$, $D$($0 \le A \le C \le W$; $0 \le B \le D \le H$)는 교차점 $(A, B)$와 교차점 $(C, D)$를 잇는 구간이 막혔음을 뜻합니다. 이 구간은 항상 도로 또는 대로의 유효한 $1$ km짜리 구간이므로 $C - A \le 1$이고 $D - B \le 1$입니다.

각 테스트 케이스에 대해, 각 날마다 대학교에 이르는 경로의 수를 $2552$로 나눈 나머지를 한 줄에 하나씩 출력합니다. 따라서 각 테스트 케이스의 출력은 정확히 $K$개의 줄로 이루어집니다.