슬레이트 모던 (라지)

슬레이트 모던 갤러리는 회색조 그림만 전시한다. 갤러리에 걸리는 그림은 $R$행 $C$열 격자여야 하고, 각 칸은 양의 정수 밝기 값으로 칠한다. 보는 사람이 놀라지 않도록, 변을 맞대고 붙어 있는 두 칸의 밝기 차이는 $D$ 이하여야 한다. 꼭짓점만 닿는 두 칸에는 이 조건이 적용되지 않는다.

화가 코디자말은 어젯밤 영감을 받아 서로 다른 칸 $N$개를 골라 양의 정수 밝기 값을 칠해 두었다. 오늘에야 갤러리의 규칙을 들은 코디자말은 남은 칸을 모두 양의 정수 밝기 값으로 채워 규칙에 맞는 그림을 완성할 수 있는지 알고 싶어 한다. 완성할 수 있다면 검은 물감을 아끼기 위해 모든 칸의 밝기 값 합을 최대로 만들려고 한다. 합이 매우 커질 수 있으므로, 최대 합을 소수 $10^9+7$로 나눈 나머지를 구한다.

첫 줄에 테스트 케이스 수 $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이고, 완성할 수 있으면 $y$는 모든 칸의 밝기 값 합의 최댓값을 $10^9+7$로 나눈 나머지이다.

• $1 \le T \le 100$
• $1 \le R \le 10^9$
• $1 \le C \le 10^9$
• $1 \le N \le 200$
• $1 \le D \le 10^9$
• 모든 $i$에 대해 $1 \le R_i \le R$, $1 \le C_i \le C$, $1 \le B_i \le 10^9$이다. $10^9$이라는 상한은 코디자말이 이미 칠한 칸에만 적용된다. 나머지 칸에는 $10^9$보다 큰 밝기 값을 써도 된다.
• $N < R \times C$이다. 즉, 비어 있는 칸이 적어도 하나 있다.
• $i \ne j$이면 $R_i \ne R_j$이거나 $C_i \ne C_j$이다. 즉, 주어지는 칸은 모두 서로 다르다.

첫 번째 예제의 1번 테스트 케이스에서 합을 최대로 만드는 그림은 다음과 같고, 합은 40이다.

6 7 9
4 6 8

2번 테스트 케이스에서 최적의 그림은 2000000000 1000000000이고 합은 3000000000이다. 이를 $10^9+7$로 나눈 나머지는 999999986이다.

3번 테스트 케이스는 완성할 수 없다. 2행 칸에 어떤 값을 넣어도 위아래로 이미 칠해진 두 칸 중 적어도 하나와 차이가 너무 커진다.

4번 테스트 케이스에서는 코디자말이 이미 칠한 두 칸의 밝기 차이가 너무 커서 그림을 이어 나갈 수 없다.