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

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

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?

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?

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$

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$

提交代码