슬레이트 모던 (스몰)

슬레이트 모던 화랑은 규칙이 엄격한 무채색 회화만 전시한다. 이 화랑에 걸리는 그림은 $R$행 $C$열 격자여야 하고, 각 칸은 양의 정수 밝기 값으로 칠한다. 그림이 너무 튀지 않도록, 변을 맞댄 두 칸(꼭짓점만 닿는 경우는 세지 않는다)의 밝기 값 차이는 $D$ 이하여야 한다.

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

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 네 정수 $R$, $C$, $N$, $D$가 주어진다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 세 정수 $R_i$, $C_i$, $B_i$가 주어지며, 격자의 $R_i$행 $C_i$열 칸의 밝기 값이 $B_i$라는 뜻이다. 행과 열 번호는 1부터 시작한다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 그림을 완성할 수 없으면 IMPOSSIBLE, 완성할 수 있으면 밝기 값 전체 합을 소수 $10^9+7$로 나눈 나머지이다.

첫 번째 테스트 케이스에서 그림을 완성하는 가장 좋은 방법은 다음과 같고, 합은 40이다.

6 7 9
4 6 8

두 번째 테스트 케이스에서 가장 좋은 방법은 2000000000 1000000000이고 합은 3000000000이다. $10^9+7$로 나눈 나머지는 999999986이다.

세 번째 테스트 케이스는 불가능하다. 2행의 칸에 어떤 값을 넣어도 이웃한 두 칸 중 적어도 하나와 차이가 너무 커진다.

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