407021: GYM102688 C Lito Lapida and the Copabanana

A Filipino proverb says: Kapag may tiyaga, may nilaga. Researchers and scholars have tried to find meaning in this proverb. Finally, they all agreed:

If one works hard to explore the forests north of Havana, one can find the Shrine of The Nilagang Saging.

A bunch of people tried to discredit their research by claiming that the researchers were going bananas, it was later found out that the scholars were correct. A shrine devoted to bananas really did exist!

In the Shrine of The Nilagang Saging, there are $$$n$$$ banana pieces indexed from $$$1$$$ to $$$n$$$. The $$$i$$$th banana piece has length $$$a_i$$$ centimeters. The number $$$a_i$$$ is a positive integer.

Legend has it that chopping the banana pieces in the correct way can earn you a fortune. However, chopping them in another way can cost you a fortune. Before chopping, one must first insert their bank card in the appropriate slot. The game then begins.

Let $$$c$$$ be a fixed integer. During the game, one can perform the following action a non-negative number of times:

Choose one of the banana pieces. Chop it into exactly two banana pieces, both having positive integer lengths of your choice. If the two banana pieces have lengths $$$b_1$$$ and $$$b_2$$$, respectively, then you earn $$$b_1b_2(b_1 + b_2 − c)$$$ pesos for doing this. Note that the sum $$$b_1 + b_2$$$ should be equal to the length $$$b$$$ of the original banana piece. If this value is negative, then its absolute value is deducted from your bank account instead.

You can quit the game at any time by removing your bank card from the slot. Of course, if there are no more valid moves, you must quit the game. What is the maximum number of pesos you can earn from this game?

The first line of input contains a single integer $$$t$$$, the number of test cases. Each test case is described with two lines.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$c$$$, the number of banana pieces and the constant $$$c$$$ for this game.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1, a_2 \dots a_n$$$, the lengths of each of the banana pieces.

For each test case, output a line containing a single integer, the answer for that test case. Since it can be quite large, output it modulo $$$10^9+7$$$.

Let $$$A$$$ be the max value of $$$a_i$$$ for a particular test case.

For all subtasks

$$$1 \le t \le 10^5$$$

$$$1 \le n \le 10^5$$$

$$$1 \le c \le 10^6$$$

$$$1 \le a_i \le 10^{18}$$$

$$$1 \le a_i \cdot c^2 \le 10^{18}$$$

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Subtask 1 (7 points):

$$$a_i \leq 10$$$

$$$t \leq 20$$$

Subtask 2 (25 points):

The sum of $$$A$$$ over all test cases is $$$\leq 1000$$$.

Subtask 3 (12 points):

The sum of $$$A$$$ over all test cases is $$$\leq 10^5$$$.

Subtask 4 (10 points):

The sum of $$$n$$$ over all test cases does not exceed $$$400$$$.

$$$a_i \leq 10^9$$$

Subtask 5 (10 points):

$$$c \leq 2$$$

Subtask 6 (8 points):

The sum of $$$n$$$ over all test cases does not exceed $$$400$$$.

The sum of $$$c$$$ over all test cases does not exceed $$$10^4$$$.

Subtask 7 (8 points):

The sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Subtask 8 (10 points):

$$$a_i \leq 10^6$$$

Subtask 9 (10 points):

No further constraints.

2
3 4
5 7 2
1 1
3

42
5