25432번 - 각성제 서브태스크

문제

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

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

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

준혁이는 하루에 2개 이상 각성제를 먹지 않으며, 주문한 각성제를 전부 먹지 않아도 된다. 준혁이가 각성제를 적절히 먹어 마지막 날까지 공부로 증가한 실력의 양이 최대가 되게 할 때 그 값을 구해보자.

입력

첫째 줄에 준혁이의 특훈 기간 $N$와 각성제의 수 $K$가 입력된다. (1ドル ≤ N,K ≤ 10,000$)

둘째 줄에는 준혁이의 특훈기간 동안 일정이 입력되는데, 만약 공부를 $x$시간 한다면 $x$ 그대로, 만약 게임을 $x$시간 한다면 $-x$로 $i$번째 날의 일정이 첫째 날부터 $N$번째 날까지 공백으로 구분되어 $N$개 입력된다. 준혁이의 하루는 24시간이 아니고 1,000,000시간이다. (1ドル ≤ \lvert x \rvert ≤ 1,000,000$)

출력

첫째 줄에 준혁이가 각성제를 적절히 먹어 얻을 수 있는 실력의 최댓값을 출력한다. 출력하는 값이 너무 커질 수 있으므로 답을 1,000,000,007ドル(10^9+7)$로 나눈 나머지를 출력한다.

얻을 수 있는 실력의 최댓값이 음수일 경우, 이를 1,000,000,007ドル(10^9+7)$로 나눈 나머지를 출력하지 않고 그대로 출력해야 한다. 얻을 수 있는 실력의 최댓값은 항상 $-2^{63}$보다 큰 수임을 증명할 수 있다.

제한

서브태스크

힌트