Phòng tranh danh giá Slate Modern chuyên về trào lưu nghệ thuật mới nhất: tranh thang xám tuân theo những quy tắc rất nghiêm ngặt. Mỗi bức tranh phải là một lưới \(R\) hàng và \(C\) cột. Mỗi ô được tô bằng một màu có độ sáng là số nguyên dương. Để bức tranh không quá chói mắt, độ sáng của hai ô chung một cạnh — không chỉ chung góc — không được chênh nhau quá \(D\).

Người bạn họa sĩ Cody-Jamal đang vẽ một bức tranh cho phòng tranh. Đêm qua, anh ấy có cảm hứng và tô sẵn \(N\) ô phân biệt bằng những độ sáng nguyên dương nhất định. Hôm nay bạn mới kể cho anh ấy về quy tắc của phòng tranh; giờ anh ấy muốn biết có thể điền độ sáng nguyên dương vào mọi ô còn lại để hoàn thành tranh mà không vi phạm quy tắc hay không. Nếu có thể, anh ấy muốn tổng độ sáng lớn nhất có thể để tiết kiệm sơn đen. Hãy tìm tổng đó hoặc xác định rằng công việc là không thể. Vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia cho số nguyên tố \(10^9+7=1000000007\).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng bốn số nguyên \(R,C,N,D\). Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa \(R_i,C_i,B_i\), cho biết ô ở hàng \(R_i\), cột \(C_i\) có độ sáng \(B_i\). Hàng và cột được đánh số từ \(1\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\). Nếu không thể hoàn thành tranh thì y là IMPOSSIBLE; nếu có thể thì y là tổng độ sáng lớn nhất có thể, lấy modulo \(1000000007\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le200\).
• \(1\le D\le10^9\).
• \(1\le R_i\le R\) và \(1\le C_i\le C\) với mọi \(i\).
• \(1\le B_i\le10^9\) với mọi \(i\). Cận trên này chỉ áp dụng cho các ô Cody-Jamal đã tô; các ô khác có thể nhận độ sáng lớn hơn \(10^9\).
• \(N<RC\); có ít nhất một ô trống.
• Với mọi \(i\ne j\), \(R_i\ne R_j\) hoặc \(C_i\ne C_j\); mọi ô cho trước đều phân biệt.

Phân nhóm

Test Set 1 (Visible): \(1\le R,C\le200\).

Test Set 2 (Hidden): \(1\le R,C\le10^9\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
2 3 2 2
2 1 4
1 2 7
1 2 1 1000000000
1 2 1000000000
3 1 2 100
1 1 1
3 1 202
2 2 2 2
2 1 1
2 2 4

Case #1: 40
Case #2: 999999986
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE

6 7 9
4 6 8

Nguồn

Google Code Jam 2017, Vòng 3, bài Slate Modern.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.