Problem:
 Score : 500 points    Problem Statement Given are N integers A_1,\ldots,A_N .  We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.  Then, print the maximum product modulo (10^9+7) , using an integer between 0 and 10^9+6 (inclusive).      Constraints  1 \leq K \leq N \leq 2\times 10^5  |A_i| \leq 10^9         Input Input is given from Standard Input in the following format:  N  K  A_1  \ldots  A_N       Output Print the maximum product modulo (10^9+7) , using an integer between 0 and 10^9+6 (inclusive).        Sample Input 1 4 2
1 2 -3 -4      Sample Output 1 12  The possible products of the two chosen elements are 2 , -3 , -4 , -6 , -8 , and 12 , so the maximum product is 12 .       Sample Input 2 4 3
-1 -2 -3 -4      Sample Output 2 1000000001  The possible products of the three chosen elements are -24 , -12 , -8 , and -6 , so the maximum product is -6 .  We print this value modulo (10^9+7) , that is, 1000000001 .       Sample Input 3 2 1
-1 1000000000      Sample Output 3 1000000000  The possible products of the one chosen element are -1 and 1000000000 , so the maximum product is 1000000000 .       Sample Input 4 10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1      Sample Output 4 999983200  Be sure to print the product modulo (10^9+7) .

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    multimul = lambda L,i=0: (L[i] * multimul(L,i+1) % P  if i+1 < len(L) else  L[i])
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    
    if N == K:
        print(multimul(A))
        return
    not_negative = []
    negative = []
    for a in A:
        if a < 0:
            negative.append(a)
        else:
            not_negative.append(a)
    if len(negative) == N and K % 2 == 1:
        print(multimul(sorted(negative,reverse=True)[:K]))
        return
    not_negative.sort(reverse=True)

    not_negative = deque(not_negative)
    negative.sort()
    negative = deque(negative)
    ans = 1
    num_multiplied = 0
    while num_multiplied < K:
        if num_multiplied == K-1 or len(negative) < 2 or len(not_negative) >= 2 and not_negative[0] * not_negative[1] > negative[0] * negative[1]:
            ans = ans * not_negative.popleft() % P
            num_multiplied += 1
        else:
            ans = ans * negative.popleft() * negative.popleft() % P
            num_multiplied += 2
    print(ans)
            


    
main()

Solution (Python):

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)
hu.sort()
seis = []
hus = []
total = []
ans = 1

if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(2, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
else:
    for i in range(1, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
for i in range(1, len(hu), 2):
    hus.append(hu[i] * hu[i - 1])

total = hus + seis
total.sort(reverse=True)
for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Solution (Python):
def solve():
    MOD = 10**9 + 7

    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    if K == N:
        ans = 1
        for A in As:
            ans *= A
            ans %= MOD
        print(ans)
        return

    As.sort(key=lambda x: abs(x))

    if max(As) < 0 and K%2 != 0:
        ans = 1
        for A in As[:K]:
            ans *= A
            ans %= MOD
        print(ans)
        return

    pos0As, negAs = [], []
    for A in As:
        if A >= 0:
            pos0As.append(A)
        elif A < 0:
            negAs.append(A)
    pos0As.sort()
    negAs.sort(reverse=True)

    ans = 1
    rest = K
    while rest > 0:
        if rest == 1:
            ans *= pos0As.pop()
            rest -= 1
        else:
            if len(pos0As) < 2:
                ans *= negAs.pop()
                ans *= negAs.pop()
                rest -= 2
            elif len(negAs) < 2:
                ans *= pos0As.pop()
                rest -= 1
            else:
                pPos0 = pos0As[-1] * pos0As[-2]
                pNeg = negAs[-1] * negAs[-2]
                if pPos0 >= pNeg:
                    ans *= pos0As.pop()
                    rest -= 1
                else:
                    ans *= negAs.pop()
                    ans *= negAs.pop()
                    rest -= 2
        ans %= MOD

    print(ans)


solve()

Solution (Python):
def solve():
    MOD = 10**9 + 7
    INF = 10**10

    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    if K == N:
        ans = 1
        for A in As:
            ans *= A
            ans %= MOD
        print(ans)
        return

    As.sort(key=lambda x: abs(x))

    if max(As) < 0 and K%2 != 0:
        ans = 1
        for A in As[:K]:
            ans *= A
            ans %= MOD
        print(ans)
        return

    As.reverse()

    ans = 1
    sgn = 1
    for A in As[:K]:
        ans *= A
        ans %= MOD
        if A < 0:
            sgn *= -1
        elif A == 0:
            sgn = 0

    if sgn >= 0:
        print(ans)
        return

    maxNeg, maxNotNeg = -INF, -INF
    minNeg, minPos = INF, INF
    for A in As[:K]:
        if A < 0:
            maxNeg = max(maxNeg, A)
        if A > 0:
            minPos = min(minPos, A)
    for A in As[K:]:
        if A < 0:
            minNeg = min(minNeg, A)
        if A >= 0:
            maxNotNeg = max(maxNotNeg, A)

    if maxNeg == -INF or maxNotNeg == -INF:
        ans *= pow(minPos, MOD-2, MOD) * minNeg
        ans %= MOD
    elif minNeg == INF or minPos == INF:
        ans *= pow(maxNeg, MOD-2, MOD) * maxNotNeg
        ans %= MOD
    else:
        if abs(maxNeg)*abs(minNeg) >= abs(minPos)*abs(maxNotNeg):
            ans *= pow(minPos, MOD-2, MOD) * minNeg
            ans %= MOD
        else:
            ans *= pow(maxNeg, MOD-2, MOD) * maxNotNeg
            ans %= MOD

    print(ans)


solve()

Solution (Python):





























mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

n,k=map(int,input().split())
a=list(map(int,input().split()))

if n==k:
    print(multarray(a))
    exit()

ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])

ap.sort(reverse=True)
am.sort()

if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)


p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

if k%2==0:
    print(multarray(ans))
    exit()





ans_cand=[]

if p!=len(ap):
    ans_cand.append(multarray(ans)*ap[p]%mod)
if p>=2:
    
    check_i=ans.index(ap[p-1]*ap[p-2])
    
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    ans_cand.append(multarray(ans))
print(max(ans_cand))

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
z=-1
p=-1
mod=10**9+7
ans=1
for i in range(n):
    if a[i]==0:
        z=i
    elif a[i]>0:
        p=i
        break
a_abs=sorted(a,key=abs,reverse=True)
if (p==-1 and k%2==1) or n==k:
    for i in range(k):
        ans*=a[n-1-i]
        ans%=mod
    print(ans%mod)
    exit()
else:
    lp=-1
    lm=-1
    f=0
    for i in range(k):
        if a_abs[i]>=0:
            lp=i
        else:
            lm=i
            f+=1
    if f%2==0:
        for i in range(k):
          ans*=a_abs[i]
          ans%=mod
        print(ans)
    else:
        fp=-1
        fm=-1
        check_p=False
        check_m=False
        for i in range(k,n):
            if not check_p and a_abs[i]>=0:
                fp=i
                check_p=True
            elif not check_m and a_abs[i]<0:
                fm=i
                check_m=True
            if check_m and check_p:
                break
        if lp!=-1:
            if fp==-1:
              for i in range(k):
                if i==lp:
                  continue
                ans*=a_abs[i]
                ans%=mod
              ans*=a_abs[fm]
              ans%=mod
            elif fm==-1:
              for i in range(k):
                if i==lm:
                  continue
                ans*=a_abs[i]
                ans%=mod
              ans*=a_abs[fp]
              ans%=mod

            else:
                if a_abs[fm]*a_abs[lm]>=a_abs[fp]*a_abs[lp]:
                  for i in range(k):
                    if i==lp:
                      continue
                    ans*=a_abs[i]
                    ans%=mod
                  ans*=a_abs[fm]
                  ans%=mod
                else:
                  for i in range(k):
                    if i==lm:
                      continue
               	    ans*=a_abs[i]
                    ans%=mod
                  ans*=a_abs[fp]
                  ans%=mod
        else:
          for i in range(k):
            if i==lm:
              continue
            ans*=a_abs[i]
            ans%=mod
          ans*=a_abs[fp]
          ans%=mod
        print(ans%mod)

Solution (Python):
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(key=abs, reverse=1)

mod = 10**9+7
ans = 1
sign = 1
for i in range(k):
    ans *= a[i]
    ans %= mod
    if a[i] < 0:
        sign *= -1
    elif a[i] == 0:
        sign = 0
if sign >= 0:
    print(ans)
else:
    t = None
    ok = True
    for i in reversed(range(k)):
        if a[i] < 0:
            break
    else:
        ok = False
    for j in range(k, n):
        if a[j] > 0:
            break
    else:
        ok = False

    if ok:
        t = (a[i], a[j])

    ok = True
    for i in reversed(range(k)):
        if a[i] > 0:
            break
    else:
        ok = False
    for j in range(k, n):
        if a[j] < 0:
            break
    else:
        ok = False

    if ok:
        if t is None:
            t = (a[i], a[j])
        else:
            if (t[1]*a[i] - t[0]*a[j]) * t[0]*a[j] < 0:
                t = (a[i], a[j])

    if t is None:
        ans = 1
        a.reverse()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)
    else:
        print(ans*t[1] * pow(t[0], mod-2, mod) % mod)

Solution (Python):
from sys import exit
from random import randrange
MOD = 10**9+7
n, k = map(int, input().split())
b = list(map(int, input().split()))
a = []
if n == k:
	ans = 1
	for x in b:
		ans *= x
		ans %= MOD
	print(ans)
	exit()
for x in b:
	if x != 0:
		a.append(x)
if len(a) < k:
	print(0)
	exit()

a.sort(key=lambda x: -abs(x))

ans = 1
minus = 0
for i in range(k):
	ans *= a[i]
	ans %= MOD
	if a[i] < 0:
		minus += 1

if minus%2 == 0:
	print(ans)
	exit()

if len(a) == k:
	if len(a) < n:
		print(0)
		exit()

for i in range(k, len(a)):
	if a[i] < 0:
		minus += 1

if minus == len(a):
	if len(a) < n:
		print(0)
		exit()
	ans = 1
	for i in range(k):
		ans *= a[-i-1]
		ans %= MOD
	print(ans)
	exit()

flg1 = False
for i in range(k-1, -1, -1):
	if a[i] * a[k] < 0:
		p, q = a[i], a[k]
		flg1 = True
		break

flg2 = False
for i in range(k, len(a)):
	if a[k-1] * a[i] < 0:
		r, s = a[k-1], a[i]
		flg2 = True
		break

if flg1 and flg2:
	if abs(q*r) >= abs(p*s):
		ans *= pow(p, MOD-2, MOD)
		ans *= q
		print(ans%MOD)
	else:
		ans *= pow(r, MOD-2, MOD)
		ans *= s
		print(ans%MOD)

elif flg1:
	ans *= pow(p, MOD-2, MOD)
	ans *= q
	print(ans%MOD)

elif flg2:
	ans *= pow(r, MOD-2, MOD)
	ans *= s
	print(ans%MOD)

else:
	print("コーナーケース多すぎん？")

Solution (Python):
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)
if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

ans=1
while k>1:
    if n_minus>1 and n_plus>1 and k!=3:
        if minus[0]*minus[1]>=plus[0]*plus[1]:
            n_minus-=2
            k-=2
            for _ in range(2):
                ans*=minus.popleft()
                ans%=mod
        else:
            n_plus-=2
            k-=2
            for _ in range(2):
                ans*=plus.popleft()
                ans%=mod
    elif n_minus>1 and n_plus>2 and k==3:
        ans*=max(minus[0]*minus[1]*plus[0],plus[0]*plus[1]*plus[2])
        ans%=mod
        k-=3
    elif n_minus>1:
        n_minus-=2
        k-=2
        for _ in range(2):
            ans*=minus.popleft()
            ans%=mod
    elif n_plus>1:
        n_plus-=2
        k-=2
        for _ in range(2):
            ans*=plus.popleft()
            ans%=mod

if k==1:
    if plus:
        ans*=plus.popleft()
        ans%=mod

print(ans)

Solution (Python):

"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

N, K = map(int, input().split())

A = list(map(int, input().split()))

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort(reverse=True)
    plus_list.sort()
    if K % 2 == 1:
        ans = plus_list.pop()
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list.pop() * ans) % mod
            ans = (minus_list.pop() * ans) % mod
        elif (len(minus_list) < 2):
            ans = (plus_list.pop() * ans) % mod
            ans = (plus_list.pop() * ans) % mod
        elif (plus_list[len(plus_list) - 1] * plus_list[len(plus_list) - 2] > minus_list[len(minus_list) - 1] * minus_list[len(minus_list) - 2]):
            ans = (plus_list.pop()* ans) % mod
            ans = (plus_list.pop() * ans) % mod
        else:
            ans = (minus_list.pop() * ans) % mod
            ans = (minus_list.pop()* ans) % mod
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10 ** 9 + 7

AA = sorted(A, key=lambda x: -abs(x))

nega1 = []
posi1 = []
for a in AA[:k]:
  if a < 0:
    nega1.append(a)
  else:
    posi1.append(a)

nega2 = []
posi2 = []
for a in AA[k:]:
  if a < 0:
    nega2.append(a)
  else:
    posi2.append(a)

if all(a < 0 for a in A) and k % 2 == 1:
  AA = sorted(A, key=lambda x: abs(x))
  nega1 = []
  posi1 = []
  for a in AA[:k]:
    nega1.append(a)

elif n == k:
  pass

elif len(nega1) % 2 != 0:
  if posi1 and nega2 and posi2:
    if abs(nega1[-1] * nega2[0]) < abs(posi1[-1] * posi2[0]):
      del nega1[-1]
      nega1.append(posi2[0])
    else:
      del posi1[-1]
      posi1.append(nega2[0])
  elif not posi1 or not nega2:
    del nega1[-1]
    nega1.append(posi2[0])
  elif not posi2:
    del posi1[-1]
    posi1.append(nega2[0])
  
a = 1
for m in posi1:
  a = (a * m) % MOD
for p in nega1:
  a = (a * p) % MOD
 
print(a)

Solution (Python):

import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7


if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD
else:
    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD
    else:
        pos.sort(reverse=True)
        dbl = []
        ans = 1
        ini = 0
        rem = K
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
            rem -= 1
        for i in range(0, (len(pos)-ini)//2):
            heapq.heappush(dbl, (pos[ini+i*2] * pos[ini+i*2+1])*-1)
        neg.sort()
        for i in range(0, len(neg)//2):
            heapq.heappush(dbl, (neg[i*2] * neg[i*2+1]) * -1)
        while rem > 0:
            ans = (ans * heapq.heappop(dbl) * -1) % MOD
            rem -= 2

print(ans)

Solution (Python):

import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7


if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD

else:
    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    
    
    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD

    
    
    
    
    
    else:
        pos.sort(reverse=True)
        pos2 = []
        ans = 1
        ini = 0
        rem = K
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
            rem -= 1
        for i in range(0, (len(pos)-ini)//2):
            heapq.heappush(pos2, (pos[i*2+ini] * pos[i*2+ini+1])*-1)
        neg.sort()
        neg2 = []
        for i in range(0, len(neg)//2):
            heapq.heappush(neg2, (neg[i*2] * neg[i*2+1]) * -1)
        while rem > 0:
            if (pos2 != [] and neg2 == []) or (pos2 != [] and neg2 != [] and pos2[0] <= neg2[0]):
                tmp = heapq.heappop(pos2) * -1
            else:
                tmp = heapq.heappop(neg2) * -1
            ans = (ans * tmp) % MOD
            rem -= 2

print(ans)

Solution (Python):
MOD = (10 ** 9) + 7
n, k  = map(int, input().split())
a = list(map(int, input().split()))
 
negs = [-x for x in a if x < 0]
non_negs = [x for x in a if x >= 0]
 
if len(non_negs) == 0 and k % 2 == 1:
    negs.sort()
    ans = 1
    for i in range(k):
        ans = ans * -negs[i] % MOD
    print(ans)
    exit()
 
negs_p, non_negs_p = 0, 0
 
negs.sort(reverse = True)
non_negs.sort(reverse = True)
 
for i in range(k):
    if negs_p == len(negs):
        non_negs_p += 1
    elif non_negs_p == len(non_negs):
        negs_p += 1
    elif negs[negs_p] > non_negs[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
 
if negs_p % 2 == 0 or k == n:
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()
 
if negs_p == len(negs) or non_negs_p == 0:
    negs_p -= 1
    non_negs_p += 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()
 
if non_negs_p == len(non_negs) or negs_p == 0:
    negs_p += 1
    non_negs_p -= 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()
 
 
a = negs[negs_p - 1]
b = negs[negs_p]
c = non_negs[non_negs_p - 1]
d = non_negs[non_negs_p]
 
if a * b > c * d:
    negs_p += 1
    non_negs_p -= 1
else:
    negs_p -= 1
    non_negs_p += 1
 
ans = 1
for i in range(negs_p):
    ans = ans * -negs[i] % MOD
for i in range(non_negs_p):
    ans = ans * non_negs[i] % MOD
print(ans)

Solution (Python):
from decimal import *

n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9 + 7

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or len(pl) == 0 or len(mi) == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)) or zero == 0:
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi) or one == 0:
        ak = [zero-1,one+1]
    else:
        if Decimal(abs(mi[one]))/Decimal(pl[zero-1]) >= Decimal(pl[zero])/Decimal(abs(mi[one-1])):
            ak = [zero-1,one+1]
        else:
            ak = [zero+1,one-1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

Solution (Python):
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or ((plus and minus) and abs(minus[0])>abs(plus[0])):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or ((plus and minus) and abs(minus[0])<abs(plus[0])):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans+=mod
        ans%=mod
    print(ans)
    exit()

if 0 in cand:
    print(0)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]


cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    if tmpp!=0:
        cand2=abs(minus[0])/abs(tmpp)
    else:
        cand2=0

if tmpp==0:
    if minus:
        ans=1
        flg=True
        for i in range(k):
            if flg and cand[i]==tmpp:
                flg=False
                continue
            ans*=cand[i]
            ans+=mod
            ans%=mod
        print((ans*minus[0])%mod)
        exit()
elif (cand1!=None and cand2==None) or ((cand1!=None and cand2!=None) and plus[0]*abs(tmpp)>=abs(minus[0]*tmpm)):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans+=mod
        ans%=mod
    print((ans*plus[0])%mod)
    exit()

elif (cand1==None and cand2!=None) or ((cand1!=None and cand2!=None) and plus[0]*abs(tmpp)<abs(minus[0]*tmpm)):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans+=mod
        ans%=mod
    print((ans*minus[0])%mod)
    exit()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    flag = False  

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
            
        print(ans % MOD)
        exit()


    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        
        
        A = sorted([abs(x) for x in A])
        for a in A[:K]:
            ans *= a
            ans %= MOD
        ans *= -1
    else:
        pos = sorted(pos)
        neg = sorted(neg, reverse=True)
        if K % 2 == 1:
            
            
            ans *= pos.pop()
            ans %= MOD

        
        pairs = []
        while len(pos) >= 2:
            x = pos.pop()
            x *= pos.pop()
            pairs.append(x)
        while len(neg) >= 2:
            x = neg.pop()
            x *= neg.pop()
            pairs.append(x)
        pairs = sorted(pairs, reverse=True)
        for p in pairs[: K // 2]:
            ans *= p
            ans %= MOD

    print(ans % MOD)

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    flag = False  

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        
        
        h = [abs(x) for x in A]
        heapq.heapify(h)

        for i in range(K):
            ans *= heapq.heappop(h)
            ans %= MOD
        ans *= -1
    else:
        hpos = [-x for x in pos]
        heapq.heapify(hpos)
        hneg = neg[:]
        heapq.heapify(hneg)
        if K % 2 == 1:
            
            
            ans *= -heapq.heappop(hpos)
            ans %= MOD

        
        pairs = []
        while len(hpos) >= 2:
            x = -heapq.heappop(hpos)
            x *= -heapq.heappop(hpos)
            heapq.heappush(pairs, -x)
        while len(hneg) >= 2:
            x = heapq.heappop(hneg)
            x *= heapq.heappop(hneg)
            heapq.heappush(pairs, -x)
        if len(pairs):
            for i in range(K // 2):
                ans *= -heapq.heappop(pairs)
                ans %= MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    MOD=10**9+7
    ans=1
    if k==1:
        ans=a[-1]
    elif a[0]>=0 or (a[-1]<0 and k%2==1):
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif a[-1]<0 and k%2==0:
        for i in a[:k]:
            ans=(ans*i)%MOD
    else:
        ans=1
        if k%2==1 and n>=3:
            ans*=a[-1]
            ans%=MOD
            l,r=0,-2
            lm=a[0]*a[1]
            rm=a[-2]*a[-3]    
        else:
            l,r=0,-1
            lm=a[0]*a[1]
            rm=a[-1]*a[-2]
        for i in range(k//2):
            if lm>=rm:
                ans*=lm%MOD
                l+=2
                if l<=n-2:
                    lm=a[l]*a[l+1]
            else:
                ans*=rm%MOD
                r-=2
                if 1<=n+r:
                    rm=a[r]*a[r-1]
            ans%=MOD
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
 
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7
 
P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]
 
def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N or len(A) == K:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)
 
ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break
 
    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop()
            K -= 1
        else:
            ans *= N.pop() * N.pop()
            K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue
 
        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue
 
        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue
 
        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Solution (Python):
def get_neg(neg_list, k, mod):
    ans = 1
    neg_list.sort(reverse=True)
    for num in neg_list[:k]:
        ans = ans * num % mod
    return ans


def get_pos(pos_list, neg_list, k, mod):
    ans = 1
    nums = []
    neg_iter = iter(sorted(neg_list))
    pos_iter = iter(sorted(pos_list, reverse=True))
    if k % 2 == 1:
        ans *= pos_iter.__next__()
        k -= 1
        
    for a, b in zip(pos_iter, pos_iter):
        nums.append(a * b)

    for a, b in zip(neg_iter, neg_iter):
        nums.append(a * b)

    nums.sort(reverse=True)
    for num in nums[:k//2]:
        ans *= num
        ans %= mod
    return ans


def get_all(num_list, mod):
    ans = 1
    for num in num_list:
        ans = ans * num % mod
    return ans


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    
    if n == k:
        ans = get_all(A, mod)
        print(ans)
        return
    
    pos_list = []
    neg_list = []

    for a in A:
        if a >= 0:
            pos_list.append(a)
        else:
            neg_list.append(a)

    if k % 2 and not pos_list:
        ans = get_neg(neg_list, k, mod)
    else:
        ans = get_pos(pos_list, neg_list, k, mod)

    print(ans)


if __name__ == "__main__":
    main()