17448번 - 성냥팔이 소년

문제

동현이는 성냥팔이 소년이다. 하지만, 요즘 같은 세상에 성냥을 사는 사람이 어디 있겠는가. 안 팔리는 성냥만 집에 잔뜩 쌓인 동현이는 성냥개비를 가지고 뭐라도 하고 놀려고 한다.

동현이는 지금 정수 N개와 성냥개비 K개를 가지고 있다. 우선, 동현이는 T라는 정수를 하나 만들고 그 값을 1로 정했다. 이후, 동현이는 N개의 정수 각각에 대해서 다음 세 가지 행동 중 하나를 할 것이다.

• 성냥개비를 사용하지 않고 그냥 넘어간다.
• 성냥개비를 1개 사용하고, -X를 T에 곱한다. (단, X는 그 정수의 원래 값)
• 성냥개비를 2개 사용하고, +X를 T에 곱한다. (단, X는 그 정수의 원래 값)

alt text

각 정수에 대해 할 수 있는 3가지 행동.

동현이는 성냥개비를 원하는 만큼 사용하여 T의 값을 최대화하고 싶다. (성냥개비를 사용하지 않아도 된다.) 하지만 동현이는 몇 번 해보다가 싫증이 나서 던져버리고 게임이나 하러 가 버렸다. 여러분은 똑똑하니까 동현이 대신 이 문제를 풀어 주자!

입력

첫 줄에 동현이가 가진 정수의 개수 N과 성냥개비의 개수 K가 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ K ≤ 2×N)

두 번째 줄에 동현이가 가진 N개의 정수들이 주어진다. 각 수들의 절댓값은 10⁹ 이하이다.

출력

동현이가 성냥개비를 적절히 사용하여 T의 값을 최대화했을 때, 그 값을 10⁹+7로 나눈 나머지를 출력한다.

제한

노트

동현이가 3, -5, 6에 각각 성냥개비 1개씩을 썼을 때 T의 값이 (-3) × 5 × (-6) = 90으로 최대이다.