著名的 Slate Modern 画廊专注于最新的艺术潮流：遵循极其严格规则的灰度画作。画廊中的任何画作都必须是一个 $R$ 行 $C$ 列的网格。网格中的每个单元格都涂有特定正整数亮度的颜色；为了确保艺术作品不会过于突兀，任何两个共享一条边（不仅仅是角）的单元格，其亮度值之差不得超过 $D$ 个单位。

你的艺术家朋友 Cody-Jamal 正在为画廊创作一幅画布。昨晚，他灵感迸发，填充了 $N$ 个特定单元格，并赋予了它们特定的正整数亮度值。你今天刚告诉他画廊的规则，现在他想知道是否有可能在不违反画廊规则的情况下，填满所有剩余的单元格并完成这幅画。如果可能，他希望所有亮度值的总和尽可能大，以节省他的黑色颜料。你能帮他找到这个总和，或者确定任务是不可能的吗？由于输出可能是一个非常大的数字，我们仅要求你输出结果除以质数 $10^9+7$ ($1000000007$) 的余数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $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（如果无法完成画作），要么是所有亮度值之和的最大可能值对质数 $10^9+7$ ($1000000007$) 取模后的结果。

数据范围

$1 \le T \le 100$ $1 \le N \le 200$ $1 \le D \le 10^9$ $1 \le R_i \le R$，$1 \le C_i \le C$，$1 \le B_i \le 10^9$（注意：上限仅适用于 Cody-Jamal 已经填充的单元格。你可以为其他单元格分配大于 $10^9$ 的亮度值。） $N < R \times C$（至少有一个空单元格） 对于所有 $i \neq j$，$R_i \neq R_j$ 或 $C_i \neq C_j$（所有给定的单元格在网格中都是不同的）

子任务 1 时间限制：20 秒 $1 \le R \le 200$ $1 \le C \le 200$

子任务 2 时间限制：40 秒 $1 \le R \le 10^9$ $1 \le C \le 10^9$

样例

输入 1

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

输出 1

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

说明

在样例 1 中，完成画作的最优方式是： 6 7 9 4 6 8 总和为 40。

在样例 2 中，完成画作的最优方式是： 2000000000 1000000000 总和为 3000000000；对 $10^9+7$ 取模后为 999999986。

在样例 3 中，任务是不可能的。无论你为第 2 行的单元格选择什么值，它与两个已填充的相邻单元格中至少一个的差值都会过大。

在样例 4 中，Cody-Jamal 填充的两个单元格的亮度值已经相差过大，因此无法继续。