Slate Modern (Large)

The Slate Modern gallery shows only grayscale paintings. Every painting in the gallery must be a grid with $R$ rows and $C$ columns, and each cell is painted with a positive integer brightness value. So that the art is not too startling, two cells that share an edge must have brightness values that differ by at most $D$. Cells that touch only at a corner are not restricted.

Last night your artist friend Cody-Jamal picked $N$ different cells and filled each of them with a positive integer brightness value. You told him the gallery rules only today, and now he wants to know whether the remaining cells can all be filled with positive integer brightness values so that the painting obeys the rules. If that is possible, he wants the sum of all brightness values to be as large as possible, to save his black paint. The sum can be very large, so report it modulo the prime $10^9+7$.

The first line contains the number of test cases $T$.

The first line of each test case contains four integers $R$, $C$, $N$, and $D$. Then $N$ lines follow. The $i$-th of them contains three integers $R_i$, $C_i$, and $B_i$, which mean that the cell in row $R_i$ and column $C_i$ already has brightness value $B_i$. Rows and columns are numbered starting from 1.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1. If the painting cannot be completed, $y$ is IMPOSSIBLE. Otherwise $y$ is the maximum possible sum of all brightness values modulo $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$
• $1 \le R_i \le R$, $1 \le C_i \le C$, and $1 \le B_i \le 10^9$ for all $i$. The upper bound of $10^9$ applies only to the cells Cody-Jamal already painted. You may assign brightness values larger than $10^9$ to the other cells.
• $N < R \times C$, so at least one cell is empty.
• $R_i \ne R_j$ or $C_i \ne C_j$ for all $i \ne j$, so the given cells are all different.

In test case 1 of the first example, one optimal painting is shown below, and its sum is 40.

6 7 9
4 6 8

In test case 2 the best painting is 2000000000 1000000000, whose sum is 3000000000. Modulo $10^9+7$ that is 999999986.

Test case 3 cannot be completed. Whatever value you choose for the cell in row 2, it differs too much from at least one of the two painted cells above and below it.

In test case 4 the two cells Cody-Jamal already painted have brightness values that are too far apart, so the painting cannot be continued.