熊猫先生喜欢玩网格纸拼图。最近，他发明了一种玩网格纸的新规则。

起初，他拿出一张有 $N$ 行 $M$ 列的网格纸。然后，他在每个单元格中填入一个 $[1, K]$ 范围内的整数。填完所有单元格后，他开始寻找网格中的“伟大单元格”（Great cells）。当且仅当一个单元格满足以下两个条件时，它被称为伟大单元格：

• 该单元格中的值严格大于同一行中的其他单元格。
• 该单元格中的值严格大于同一列中的其他单元格。

现在，熊猫先生想知道有多少种不同的填法，使得网格中恰好有 $g$ 个伟大单元格。

由于熊猫先生喜欢简单的结论数字，让我们直接告诉他以下数值：

$$\sum_{g=0}^{NM} (g + 1) \cdot A_g \pmod{10^9 + 7}$$

其中 $A_g$ 表示熊猫先生填满网格纸且恰好有 $g$ 个伟大单元格的不同方案数。

输入格式

第一行输入包含测试用例的数量 $T$。接下来有 $T$ 行。 每一行代表一个测试用例，包含 3 个整数 $N, M$（表示网格纸的行数和列数）以及 $K$（表示填入数字的范围）。

输出格式

对于每个测试用例，首先输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是熊猫先生要求的结论数字。

数据范围

• $1 \le T \le 20$
• $1 \le N, M, K \le 200$

样例

样例输入 1

3
2 2 2
2 3 2
3 4 5

样例输出 1

Case #1: 24
Case #2: 88
Case #3: 487890625

说明

对于第一个样例，$A_0 = 10, A_1 = 4, A_2 = 2, A_3 = A_4 = 0$，因此答案为 $10 + 4 \times 2 + 2 \times 3 = 24$。