각성제

준혁이는 알고리즘 고수가 되기 위해 특훈을 한다. 특훈 기간에는 어떤 날은 공부만 하고, 어떤 날은 게임만 한다.

준혁이의 특훈은 $N$일 동안 이루어진다. 특훈 기간에 공부를 1시간 하면 실력이 1만큼 오르고, 게임을 1시간 하면 실력이 1만큼 줄어든다. 첫째 날에 공부를 5시간 하고 둘째 날에 게임을 3시간 했다면, 증가한 실력의 총량은 2이다. 준혁이는 특훈 기간의 공부 효율을 극대화하려고 특별한 효과가 있는 각성제를 $K$개 주문했다. 각성제를 먹으면 그날부터 각성 상태가 되며, 해당 날짜를 포함해 이후에 하는 모든 공부와 게임의 효과가 2배가 된다.

각성제의 효과는 중첩된다. 예를 들어 1일차에 각성제를 먹고 2일차에 또 먹으면, 3일차에는 공부를 1시간만 해도 실력이 4만큼 오른다. 반대로 3일차에 게임을 1시간 하면 실력이 4만큼 줄어든다.

준혁이는 하루에 각성제를 1개 이하로 먹으며, 주문한 각성제를 전부 먹지 않아도 된다. 각성제를 적절히 먹어 마지막 날까지 공부로 증가한 실력의 합을 최대로 만들 때, 그 값을 구하라.

첫째 줄에 준혁이의 특훈 기간 $N$과 각성제의 수 $K$가 주어진다. ($1 \le N,K \le 10,000$)

둘째 줄에는 특훈 기간의 일정이 주어진다. $i$번째 날에 공부를 $x$시간 하면 $x$, 게임을 $x$시간 하면 $-x$로 표시되며, 첫째 날부터 $N$번째 날까지 공백으로 구분된 $N$개의 정수로 주어진다. 준혁이의 하루는 24시간이 아니라 1,000,000시간이다. ($1 \le |x| \le 1,000,000$)

준혁이가 각성제를 적절히 먹어 얻을 수 있는 실력의 최댓값을 $1,000,000,007$($10^9+7$)로 나눈 나머지로 출력한다.

최댓값이 음수이면 나머지를 구하지 않고 그대로 출력한다.

얻을 수 있는 실력의 최댓값은 항상 $-2^{63}$보다 크다는 것을 증명할 수 있다.