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

Hint

liuyiding

Source

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

提交代码