Alice 和 Bob 准备玩一个“二分搜索游戏”。游戏在一个由 $2^L$ 个单元格组成的单行棋盘上进行。每个单元格包含一个 $1$ 到 $N$ 之间的整数（包含 $1$ 和 $N$）。此外，还有编号为 $1$ 到 $N$ 的卡片。在游戏开始前，裁判会在每张卡片上写下一个 $1$ 到 $M$ 之间的整数，共有 $M^N$ 种可能的写法。Alice 和 Bob 在游戏开始前已知棋盘上每个单元格的数字以及每张卡片上的数字。

游戏轮流进行，Alice 先手。总共有 $L$ 轮，这意味着 Alice 进行 $\lceil L/2 \rceil$ 轮，Bob 进行 $\lfloor L/2 \rfloor$ 轮。在每一轮中，玩家可以选择消除剩余单元格的最左半部分或最右半部分。例如，考虑一个包含数字 $[2, 4, 1, 1, 4, 5, 2, 5]$ 的棋盘。在第一轮中，Alice 必须选择消除一半，留下 $[2, 4, 1, 1]$ 或 $[4, 5, 2, 5]$。如果她消除了最左半部分并留下 $[4, 5, 2, 5]$，那么 Bob 必须在留下 $[4, 5]$ 和 $[2, 5]$ 之间做出选择。如果他留下 $[2, 5]$，游戏的最后一轮将由 Alice 在 $[2]$ 和 $[5]$ 之间做出选择。

当游戏结束时，他们查看仅剩的那个单元格中的数字 $X$。游戏的得分是写在 $X$ 号卡片上的整数。在上面的例子中，如果 Alice 在最后一轮消除 $[5]$ 并留下 $[2]$，那么游戏的得分就是裁判写在 $2$ 号卡片上的数字。

Alice 的策略是最大化游戏得分，而 Bob 的策略是最小化游戏得分。给定一个固定的棋盘及其单元格中的整数 $A_1, A_2, \dots, A_{2^L}$。为了公平起见，他们将进行 $M^N$ 场游戏，裁判在每一场游戏中会选择一种不同的方式在卡片上书写整数。这意味着对于卡片上整数的每一种书写方式，Alice 和 Bob 都会进行一场游戏。给定游戏参数和固定的棋盘内容，请计算所有这些游戏得分的总和。由于输出可能非常大，请输出结果除以质数 $10^9 + 7$ ($1000000007$) 的余数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行。第一行包含三个整数 $N, M$ 和 $L$。第二行包含 $2^L$ 个整数 $A_1, A_2, \dots, A_{2^L}$，其中 $A_i$ 是棋盘上从左往右第 $i$ 个单元格中的整数。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有 $M^N$ 场游戏得分的总和，对质数 $10^9 + 7$ ($1000000007$) 取模的结果。

数据范围

$1 \le T \le 12$ $1 \le L \le 5$ $1 \le A_i \le N$，对于所有 $i$。

子任务 1

$1 \le N \le 8$ $1 \le M \le 100$

子任务 2

$1 \le N \le 32$ $1 \le M \le 10^9$

样例

样例输入 1

3
2 2 2
2 1 1 1
4 3 2
3 1 1 4
5 100 3
2 4 1 1 4 5 2 5

样例输出 1

Case #1: 6
Case #2: 144
Case #3: 991661422

说明 1

在样例 #1 中，在空白卡片上书写整数的方法有 $2^2 = 4$ 种：$[1, 1], [1, 2], [2, 1]$ 和 $[2, 2]$。在前两种方式中，无论 Alice 在第一轮如何选择，Bob 总能使最后一个剩余单元格中的数字为 $1$，而 $1$ 号卡片上写着 $1$，这意味着这两场游戏的得分均为 $1$。在后两种方式中，Alice 可以先消除棋盘的最左半部分，留下 $[1, 1]$ 给 Bob，他随后别无选择，只能在最后留下 $[1]$。由于在这些方式中 $1$ 号卡片上写着 $2$，因此这两场游戏的得分均为 $2$。所有得分的总和因此为 $1 + 1 + 2 + 2 = 6$。

Figure 1. Illustration of the binary search game process on a board with numbers [2, 4, 1, 1, 4, 5, 2, 5], showing the elimination steps and the final selection of card 2.