Slate Modern (Small)

The Slate Modern gallery shows only grayscale paintings that follow strict rules. A painting in this gallery must be a grid with $R$ rows and $C$ columns, and every cell is painted with a positive integer brightness value. So that a painting is not too jarring, any two cells that share an edge (sharing only a corner does not count) must have brightness values that differ by at most $D$.

Your artist friend Cody-Jamal is working on a canvas for the gallery. Last night he filled in $N$ different cells with positive integer brightness values. He heard the gallery rules only today, and now he wants to know whether every remaining cell can be filled with a positive integer brightness value without breaking the rules. If the painting can be finished, he wants the sum of all brightness values to be as large as possible so that he saves black paint. Find that sum, or report that finishing the painting is impossible. The sum can be very large, so print it modulo the prime $10^9+7$.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case begins with one line holding four integers $R$, $C$, $N$, and $D$. Then $N$ lines follow. The $i$-th of them holds three integers $R_i$, $C_i$, and $B_i$, meaning that the cell in row $R_i$ and column $C_i$ has brightness value $B_i$. Rows and columns are numbered from 1.

Limits

• $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$
• $1 \le R_i \le R$ and $1 \le C_i \le C$ for all $i$
• $1 \le B_i \le 10^9$ for all $i$. This upper bound 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.
• If $i \ne j$ then $R_i \ne R_j$ or $C_i \ne C_j$, so all of the given cells are different.

For each test case, print one line of the form Case #x: y, where x is the test case number starting from 1 and y is IMPOSSIBLE if the painting cannot be finished, and otherwise the maximum possible sum of all brightness values modulo the prime $10^9+7$.

In the first test case the best way to finish the painting is

6 7 9
4 6 8

and the sum is 40.

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

The third test case is impossible. Whatever value goes into the cell in row 2, it differs too much from at least one of its two painted neighbors.

The fourth test case is impossible because the two cells Cody-Jamal already painted have brightness values that are too far apart.