Stimulant

Junhyuk takes special training to become an expert in algorithms. During the training period, on some days he only studies, and on other days he only plays games.

Junhyuk's training lasts $N$ days. Each hour of studying during the training period raises his skill by 1, and each hour of gaming lowers it by 1. If he studies for 5 hours on day 1 and plays games for 3 hours on day 2, the total increase in skill is 2. To maximize the efficiency of his studying, Junhyuk orders $K$ stimulants with a special effect. When he takes a stimulant, he becomes awakened from that day on. Every hour of studying and gaming from that day, including that day, has double effect.

The effects of stimulants stack. For example, if he takes a stimulant on day 1 and another on day 2, then on day 3, one hour of studying raises his skill by 4. Conversely, one hour of gaming on day 3 lowers his skill by 4.

Junhyuk takes at most one stimulant per day, and he does not have to take all $K$ stimulants he ordered. Find the maximum total skill gained from studying by the last day, when he takes the stimulants appropriately.

The first line contains $N$ and $K$ ($1 \le N,K \le 10,000$).

The second line contains $N$ integers separated by spaces. On day $i$, if he studies for $x$ hours, the value is $x$. If he plays games for $x$ hours, the value is $-x$. A day in Junhyuk's training is 1,000,000 hours, not 24. ($1 \le |x| \le 1,000,000$)

Print the maximum skill Junhyuk can gain by taking stimulants appropriately, taken modulo $1,000,000,007$ ($10^9+7$). If the maximum is negative, print it as is, without taking the modulo.

It can be proven that the maximum is always greater than $-2^{63}$.