슬레이트 모던

명망 높은 Slate Modern 미술관은 최신 미술 유행인, 매우 엄격한 규칙을 따르는 회색조 회화를 전문으로 한다. 미술관의 모든 그림은 R개의 행과 C개의 열로 이루어진 격자여야 한다. 격자의 각 칸은 특정한 양의 정수 밝기 값에 해당하는 색으로 칠해진다. 작품이 시각적으로 지나치게 자극적이지 않도록, 모서리만이 아니라 변을 공유하는 임의의 두 칸의 밝기 값 차이는 D단위 이하여야 한다.

화가인 친구 Cody-Jamal은 미술관에 출품할 캔버스를 작업하고 있다. 어젯밤 그는 영감을 받아 서로 다른 특정한 N개의 칸을 각각 특정한 양의 정수 밝기 값으로 칠했다. 오늘 당신이 미술관의 규칙을 알려 주자, 그는 남은 모든 칸을 양의 정수 밝기 값으로 채워 미술관의 규칙을 어기지 않고 그림을 완성할 수 있는지 알고 싶어 한다. 가능하다면 검은색 물감을 아끼기 위해 밝기 값의 합을 가능한 한 크게 만들고 싶어 한다. 이 합을 구하거나 작업이 불가능하다고 판정하도록 도와줄 수 있는가? 출력값이 매우 큰 수일 수 있으므로, 결과를 소수 $10^{9}$+7 (1000000007)로 나눈 나머지만 출력하면 된다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ 200. 1 ≤ D ≤ $10^{9}$. 모든 i에 대해 1 ≤ $R_{i}$ ≤ R. 모든 i에 대해 1 ≤ $C_{i}$ ≤ C. 모든 i에 대해 1 ≤ $B_{i}$ ≤ $10^{9}$. (상한은 Cody-Jamal이 이미 칠한 칸에만 적용된다는 점에 유의하라. 다른 칸에는 $10^{9}$보다 큰 밝기 값을 지정할 수 있다.) N < R × C. (빈 칸이 적어도 하나 있다.) 모든 i ≠ j에 대해 $R_{i}$ ≠ $R_{j}$ 그리고/또는 $C_{i}$ ≠ $C_{j}$. (주어진 모든 칸은 격자에서 서로 다른 칸이다.)

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 40초. 1 ≤ R ≤ 200. 1 ≤ C ≤ 200.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 80초. 1 ≤ R ≤ $10^{9}$. 1 ≤ C ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 네 정수 R, C, N, D가 있는 한 줄로 시작한다. 그다음에는 N개의 줄이 주어진다. 이 중 i번째 줄에는 세 정수 $R_{i}$, $C_{i}$, $B_{i}$이 있으며, 이는 격자의 $R_{i}$번째 행과 $C_{i}$번째 열에 있는 칸의 밝기 값이 $B_{i}$임을 나타낸다. 격자의 행과 열 번호는 1부터 시작한다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y은 그림을 완성할 수 없다면 IMPOSSIBLE이고, 그렇지 않다면 가능한 모든 밝기 값의 합의 최댓값을 소수 $10^{9}$+7 (1000000007)로 나눈 나머지이다.

예제 케이스 #1에서 그림을 완성하는 최적의 방법은 다음과 같다.

6 7 9 4 6 8

그 합은 40이다.

예제 케이스 #2에서 그림을 완성하는 최적의 방법은 다음과 같다.

2000000000 1000000000

그 합은 3000000000이며, 이를 $10^{9}$+7로 나눈 나머지는 999999986이다.

예제 케이스 #3에서는 작업이 불가능하다. 2행의 칸에 어떤 값을 선택하더라도, 인접한 두 개의 이미 채워진 칸 중 적어도 하나와의 차이가 너무 크다.

예제 케이스 #4에서는 Cody-Jamal이 이미 채운 두 칸의 밝기 값 차이가 너무 크므로 계속 진행할 수 없다.