# Mr. Panda and Circles

Time Limit: 40000/20000 MS (Java/Others)

Memory Limit: 65536/524288 K (Java/Others)

## Description

Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle while he was playing the following game with Mrs. Panda:
In a plane, there are M points $(0,0),(1,0), ..,(M-2,0),(M-1,0)$ in a segment. You are also given $N$ circles, the radius of $i^{th}$ circle is $R_i$. In the game, you are allowed to put center of any circle into one of the $M$ points without making circles overlap (that is, if the intersection of their circles has a positive area).
An arrangement of circles is considered as valid if every circle’s center is in one of the $M$ points. Mr. Panda wanted to know length of empty units which are not covered by any circle in the segment from $(0,0)$ to $(M-1,0)$.
Because there are too many arrangements, Mr. Panda only wanted to know $\sum L_i^2$ modulo $1,000,000,007$ where $L_i$ is length of empty units in the $i^{th}$ arrangement.
The puzzle has confused Mr. Panda for a long time. Luckily, Mr. Panda knows you are in this contest. Could you help Mr. Panda’s solve the puzzle?

## Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case starts with a line consisting of two integers $N$, the number of circles, and $M$, the number
of points.
Then, a line consisting of $N$ integer numbers follows, the $i^{th}$ number $R_i$ indicates radius of the $i^{th}$ circle.
$1 \leq T \leq 50$
$1 \leq N \leq 10^5$
$2 \leq M \leq 10^{18}$
$1 \leq R_i \leq 10^5$

## Output

For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the number that Mr. Panda wants to know for the $i^{th}$ input data set.

## Sample Input

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

## Sample Output

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



liuyiding

## Source

2017中国大学生程序设计竞赛-总决赛-重现赛（感谢哈工大）