熊猫先生喜欢创作和解决数学谜题。有一天，熊猫先生在和熊猫夫人玩游戏时想出了一个谜题：

在平面上，线段上有 $M$ 个点 $(0, 0), (1, 0), \dots, (M-2, 0), (M-1, 0)$。同时给定 $N$ 个圆，第 $i$ 个圆的半径为 $R_i$。在游戏中，你可以将任意圆的圆心放置在上述 $M$ 个点中的某一个上，且不能使圆重叠（即如果两个圆的交集面积为正，则视为重叠），并且必须使用所有的圆。

如果每个圆的圆心都在这 $M$ 个点中的某一个上，则称该圆的排列是合法的。熊猫先生想知道在从 $(0, 0)$ 到 $(M-1, 0)$ 的线段上，没有被任何圆覆盖的空余单位长度。

由于排列方式太多，熊猫先生只想知道 $\sum L_i^2 \pmod{1,000,000,007}$，其中 $L_i$ 是第 $i$ 种排列中空余单位的长度。

这个谜题困扰了熊猫先生很久。幸运的是，熊猫先生知道你正在参加这场比赛。你能帮熊猫先生解决这个谜题吗？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$（圆的数量）和 $M$（点的数量）。 接下来一行包含 $N$ 个整数，第 $i$ 个数 $R_i$ 表示第 $i$ 个圆的半径。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是熊猫先生想要知道的对于第 $x$ 个输入数据集的结果。

数据范围

• $1 \le T \le 30$
• $1 \le N \le 10^5$
• $2 \le M \le 10^{18}$
• $1 \le R_i \le 10^5$

样例

输入 1

5
3 6
1 1 1
2 5
1 2
2 6
1 2
3 2
1 1 1
1 10
50

输出 1

Case #1: 12
Case #2: 2
Case #3: 14
Case #4: 0
Case #5: 0

说明

在第二个样例中，一种包含空余单位的排列如下：

另一种包含空余单位的排列可以通过将上述排列镜像得到。显然，不存在包含两个或更多空余单位的排列。因此答案为 $1^2 + 1^2 = 2$。