410306: GYM104008 C Array Concatenation

Little relyt871 has a magical machine. In each operation, his machine can do one of the following operations to the input array $$$b$$$:

• Generate a copy of $$$b$$$ and concatenate it after $$$b$$$. More formally, the resulting array should be $$$$$$b' = \{b_1, b_2, \dots, b_{|b|}, b_1, b_2, \dots, b_{|b|}\}.$$$$$$
• Generate a copy of $$$b$$$, reverse it, then concatenate it before $$$b$$$. More formally, the resulting array should be $$$$$$b' = \{b_{|b|}, b_{|b-1|}, \dots, b_{1}, b_1, b_2, \dots, b_{|b|}\}.$$$$$$

Initially, he has an array $$$a$$$ of length $$$n$$$. Then, he wants to operate the machine exactly $$$m$$$ times using the array on his hand while maximizing the sum of all prefix sums of the final array. Since he has a somewhat finite brain, when he adds some integers, he only cares about the sum modulo $$$1\,000\,000\,007$$$. Formally, suppose after all $$$m$$$ operations he has array $$$b$$$ of length $$$n'$$$, he wants to maximize the following value: $$$$$$\Big(\sum_{i=1}^{n'}\sum_{j=1}^{i}b_j\Big) \pmod{1\,000\,000\,007}.$$$$$$

Please note that you should maximize the value after taking the modulo: the array with answer $$$1\,000\,000\,007$$$ before taking the modulo is considered less than the array with answer $$$1$$$.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n,m\leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,\ a_2, ...,\ a_n$$$ ($$$1 \leq a_i \leq 10^{9}$$$) separated by spaces.

Print a single integer in one line, denoting the answer.

2 1
1 2

15

5 10
26463 39326 86411 75307 85926

806275469