4486: 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₁,b₂,…,b_|b|,b₁,b₂,…,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|,…,b₁,b₁,b₂,…,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: 
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<= n,m<= 10⁵).
The second line contains n integers a₁, a₂, ..., a_n (1 <= a_i <= 10⁹) separated by spaces.

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

2 1
1 2

15

input

5 10
26463 39326 86411 75307 85926

output

806275469