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):
from collections import deque
import sys
input=sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt=k

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    num=0
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:
                ans *=B.popleft()
                num=1
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        else:
            ans *=B.popleft()*C.popleft()
            flag=0
        k -=2-num
    else:
        if 0<length_B:ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

neg_a = sorted([a for a in A if a < 0], reverse=True)
pos_a = sorted([a for a in A if a >= 0])
ans = 1

if len(pos_a) == 0 and K % 2 == 1:
    for a in neg_a[:K]:
        ans = ans * a % MOD
    print(ans)
    exit()

while K > 0:
    if K == 1 or len(neg_a) <= 1:
        if len(pos_a) == 0:
            ans *= neg_a.pop()
        elif len(pos_a) > 0:
            ans *= pos_a.pop()
        K -= 1
    elif len(pos_a) <= 1:
        ans *= neg_a.pop() * neg_a.pop()
        K -= 2
    elif pos_a[-1] * pos_a[-2] > neg_a[-1] * neg_a[-2]:
        ans *= pos_a.pop()
        K -= 1
    else:
        ans *= neg_a.pop() * neg_a.pop()
        K -= 2
    ans %= MOD

print(ans)

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
for a in A:
    if a >= 0:
        B.append(a)
    else:
        C.append(-a)

ans = 1
if len(B) == 0 and K % 2 == 1:
    C = sorted(C)
    for i in range(K):
        ans *= -C[i]
        ans %= MOD
    print(ans)
    sys.exit()
      
negs_p = 0
non_negs_p = 0
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
        
if N == K or negs_p % 2 == 0:
    for i in range(non_negs_p):
        ans = ans * B[i] % MOD
    for i in range(negs_p):
        ans = ans * -C[i] % MOD
    print(ans)
    sys.exit()

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:
        negs_p -= 1
        non_negs_p += 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        negs_p += 1
        non_negs_p -= 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            negs_p += 1
            non_negs_p -= 1
        else:   
            negs_p -= 1
            non_negs_p += 1
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
print(ans)

Solution (Python):
import sys
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))

X = 1

if N == K:
    for a in A:
        X = X * a % MOD
        X %= MOD
    print(X)
    sys.exit()

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

if len(P) == 0:
    if K % 2 != 0:
        M.sort(reverse=True)
        for i in range(K):
            X = X * M[i] % MOD
            X %= MOD
        print(X)
        sys.exit()

P.sort()
M.sort(reverse=True)

if K % 2 != 0:
    X = X * P[-1] % MOD
    X %= MOD
    K -= 1
    P.pop()

PP = []
if len(P) % 2 == 0:
    for i in range(0, len(P), 2):
        PP.append(P[i] * P[i + 1])
else:
    PP.append(P[0])
    for i in range(1, len(P), 2):
        PP.append(P[i] * P[i + 1])
if len(M) % 2 == 0:
    for i in range(0, len(M), 2):
        PP.append(M[i] * M[i + 1])
else:
    for i in range(1, len(M), 2):
        PP.append(M[i] * M[i + 1])
PP.sort(reverse=True)

i = 0
while K > 0:
    X = X * PP[i] % MOD
    X %= MOD
    K -= 2
    i += 1

print(X)

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n or k>len(pos)+len(neg)):
    for el in a:
        ans = (ans%mod*el%mod)%mod
elif(len(pos)+len(neg)==k):
    if(len(neg)%2!=0):
        ans = 0
    else:
        for el in pos:
            ans = (ans%mod*el%mod)%mod
        for el in neg:
            ans = (ans%mod*el%mod)%mod

else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            if(0 in a):
                ans = 0
            else:
                for i in range(len(neg) - 1):
                    if (temp == k):
                        break
                    ans = (ans%mod * neg[i]%mod) % mod
                    temp += 1
                if (temp < k):
                    ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2>=-1 and i-2<=len(pos)-1 and j-2<=len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            
            ans = max(ans, ans1)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

m = 1000000007

a = [e for e in A if e > 0]
b = [e for e in A if e < 0]
c = [e for e in A if e == 0]

if len(a) >= K - (min(K, len(b)) // 2) * 2:
    a.sort(reverse=True)
    b.sort()
    result = 1
    i = 0
    j = 0
    k = 0
    while k < K:
        if k < K - 1 and i < len(a) - 1 and j < len(b) - 1:
            x = a[i] * a[i + 1]
            y = b[j] * b[j + 1]
            if y >= x:
                result *= y
                result %= m
                j += 2
                k += 2
            else:
                result *= a[i]
                result %= m
                i += 1
                k += 1
        elif k < K - 1 and j < len(b) - 1:
            y = b[j] * b[j + 1]
            result *= y
            result %= m
            j += 2
            k += 2
        elif i < len(a):
            result *= a[i]
            result %= m
            i += 1
            k += 1
        elif j < len(b):
            result *= b[j]
            result %= m
            j += 1
            k += 1
    print(result)

elif len(c) != 0:
    print(0)

else:
    a.sort()
    b.sort(reverse=True)
    result = 1
    i = 0
    j = 0
    k = 0
    while k < K:
        if i < len(a) and j < len(b):
            if a[i] <= -b[i]:
                result *= a[i]
                result %= m
                i += 1
                k += 1
            else:
                result *= b[j]
                result %= m
                j += 1
                k += 1
        elif i < len(a):
            result *= a[i]
            result %= m
            i += 1
            k += 1
        elif j < len(b):
            result *= b[j]
            result %= m
            j += 1
            k += 1
    print(result)

Solution (Python):
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
s, t = [], []  
for i in a:
  if i < 0:
    t.append(i)
  else:
    s.append(i)
S, T = len(s), len(t)
is_positive = False  
if S > 0:
  
  if n == k:
    
    is_positive = (T % 2 == 0) 
  else:
    is_positive = True
else:
  is_positive = (k % 2 == 0)

ans = 1
if not is_positive:
  a.sort(key=abs)
  for i in range(k):
    ans = ans * a[i] % MOD
else:
  s.sort()
  t.sort(reverse=True)
  if k % 2 == 1:
    ans = ans * s.pop(-1) % MOD
  p = []
  while(len(s) >= 2):
    x = s.pop(-1)
    x *= s.pop(-1)
    p.append(x)
  while(len(t) >= 2):
    x = t.pop(-1)
    x *= t.pop(-1)
    p.append(x)
  p.sort(reverse=True)
  for i in range(k // 2):
    ans = ans * p[i] % MOD
print(ans)

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)
    minus.sort()
    mod = 10**9 + 7

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
    elif P == 0:
        if K % 2 == 1:
            minus.sort(reverse=True)
        for i in range(K):
            ans *= minus[i]
            ans %= mod
    else:  
        id = 0
        if K % 2 == 1:
            ans = plus[0]
            id = 1
            P -= 1
            K -= 1
        pp = [plus[i] * plus[i+1] for i in range(id, P-1+id, 2)]
        mm = [minus[i] * minus[i+1] for i in range(0, M-1, 2)]

        id = 0
        id2 = 0

        for i in range(K // 2):
            if id < P // 2 and (id2 >= M // 2 or pp[id] >= mm[id2]):
                ans *= pp[id]
                id += 1
            else:
                ans *= mm[id2]
                id2 += 1
            ans %= mod

    print(ans % mod)


main()

Solution (Python):
N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD


elif all(l<0 for l in L) and K%2==1:
    
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        ans_cand_min_pos=None
        remain_cand_max_neg=None
        remain_cand_max_pos=None

        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a
                break

        

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
        for a in remain:
            if a<=0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_pos*remain_cand_max_pos)
            B = abs(ans_cand_min_neg*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Solution (Python):
def main() :
    N,K=map(int,input().split())              
    A=list(map(int,input().split()))
    mod=10**9+7
    
    minusA=sorted([i for i in A if i < 0], reverse=True) 
    plusA=sorted([i for i in A if i >= 0])               
 
    start=1
    if len(plusA)==0 and K%2==1 :        
        for i in minusA[:K] :
            start=start*i%mod
        print(start)
        exit()

    while K>0 :
        if K== 1 or len(minusA)<=1 :     
            if len(plusA)==0 :           
                start*=minusA.pop()
            elif len(plusA)>0 :          
                start*=plusA.pop()
            K-=1                         

        elif len(plusA)<= 1 :            
            start*=minusA.pop()*minusA.pop()
            K-=2

        elif plusA[-1]*plusA[-2]>minusA[-1]*minusA[-2] :
            start*=plusA.pop()
            K-=1

        elif plusA[-1]*plusA[-2]<=minusA[-1]*minusA[-2] :
            start*=minusA.pop()*minusA.pop()
            K-=2

        start%=mod
    else :
        print(start)



if __name__=="__main__" :
    main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
plus,minus,zero = 0,0,0
for i in range(n):
    if a[i] > 0:
        plus += 1
    elif a[i] < 0:
        minus += 1
    else:
        zero += 1
if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans=ans%(10**9+7)
    print(ans)
else:
    if k%2==1 and minus==n:
        a.sort(reverse=True)
        ans=1
        for i in range(k):
            ans*=a[i]
            ans=ans%(10**9+7)
        print(ans)
    else:
        l=[]
        for i in range(n):
            if a[i]>=0:
                fugou=1
            else:
                fugou=-1
            l.append((abs(a[i]),fugou))
        l.sort(reverse=True)
        ans=1
        hu=1
        for i in range(k):
            ans*=l[i][0]
            ans=ans%(10**9+7)
            hu*=l[i][1]
        if hu==1:
            print(ans)
        elif ans==0:
            print(0)
        else:
            ss,sh,ts,th=-1,-1,-1,-1
            for i in range(k)[::-1]:
                if l[i][1]>0:
                    ss=l[i][0]
                    break
            for i in range(k)[::-1]:
                if l[i][1]<0:
                    sh=l[i][0]
                    break
            for i in range(k,n):
                if l[i][1]>0:
                    ts=l[i][0]
                    break
            for i in range(k,n):
                if l[i][1]<0:
                    th=l[i][0]
                    break
            if ss>0 and sh>0 and ts>0 and th>0:
                if th*sh>=ts*ss:
                    ans=(ans*pow(ss,10**9+5,10**9+7)*th)%(10**9+7)
                else:
                    ans=(ans*pow(sh,10**9+5,10**9+7)*ts)%(10**9+7)
                print(ans)
            else:
                if th>0 and ss>0:
                    ans=(ans*pow(ss,10**9+5,10**9+7)*th)%(10**9+7)
                else:
                    ans=(ans*pow(sh,10**9+5,10**9+7)*ts)%(10**9+7)
                print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

plus,minus,zero = 0,0,0
for i in range(N):
    if A[i] > 0:
        plus += 1
    elif A[i] < 0:
        minus += 1
    else:
        zero += 1

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= MOD
    print(ans)

else:
    if K%2 == 1 and minus == N: 
        A.sort(reverse=True)

        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)

    else: 
        l = []
        for i in range(N):
            if A[i] < 0:
                fugou = -1
            else:
                fugou = 1
            l.append((abs(A[i]),fugou))
        l.sort(reverse=True)
        

        ans = 1
        fu = 0
        for i in range(K):
            if l[i][1] < 0:
                fu += 1
            ans *= l[i][0]
            ans %= MOD

        if fu%2 == 0:
            print(ans)
        elif ans == 0:
            print(0)
        else:
            sei_suteru = -1
            fu_suteru = -1
            for i in range(K)[::-1]:
                if sei_suteru == -1:
                    if l[i][1] > 0:
                        sei_suteru = l[i][0]
                if fu_suteru == -1:
                    if l[i][1] < 0:
                        fu_suteru = l[i][0]
                
            sei_ireru = -1
            fu_ireru = -1
            for i in range(K,N):
                if sei_ireru == -1:
                    if l[i][1] > 0:
                        sei_ireru = l[i][0]
                if fu_ireru == -1:
                    if l[i][1] < 0:
                        fu_ireru = l[i][0]

            
            
            if sei_suteru >= 0 and fu_suteru >= 0 and sei_ireru >= 0 and fu_ireru >= 0:
                if sei_ireru*sei_suteru <= fu_ireru*fu_suteru: 
                    ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                    ans %= MOD
                else: 
                    ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                    ans %= MOD
            elif sei_ireru == -1 or fu_suteru == -1:
                ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                ans %= MOD
            else:
                ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                ans %= MOD

            print(ans)

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7


if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        ans=ans%mod
        
        if p_pos<len(purasu) and m_pos+1 < len(mainasu) and cnt<k-1:
            
            if cnt<=k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    if cnt==k-2:
                        ans*=purasu[p_pos]%mod
                        p_pos+=1
                        ans*=purasu[p_pos]%mod
                        p_pos+=1
                        cnt+=2
                    else:
                        ans*=purasu[p_pos]%mod
                        p_pos+=1
                        cnt+=1

                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)










else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
        ans=ans%mod
    
    print((-1*ans)%mod)

Solution (Python):
from functools import reduce

mod = 10**9+7

def modcumprod(*args):
    return reduce(lambda x, y: x*y%mod, args)

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

if n == k:
    print(modcumprod(*a))
elif max(a) < 0 and k % 2 == 1:
    a.sort(reverse=True)
    print(modcumprod(*a[:k]))
else:
    a.sort(key=abs, reverse=True)
    res = 1
    cnt_neg = 0
    pos1 = neg1 = 0
    for e in a[:k]:
        res *= e
        res %= mod
        if e > 0:
            pos1 = e
        else:
            cnt_neg += 1
            neg1 = e

    if res == 0 or cnt_neg % 2 == 0:
        print(res)
    else:
        pos2 = neg2 = 0
        for e in a[k:]:
            if e > 0 and not pos2:
                pos2 = e
            elif e < 0 and not neg2:
                neg2 = e
            if pos2 and neg2:
                break
        if abs(pos1 * pos2) < abs(neg1 * neg2) and pos1:
            res *= pow(pos1, -1, mod)
            res *= neg2
            res %= mod
        else:
            res *= pow(neg1, -1, mod)
            res *= pos2
            res %= mod
        print(res)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus=[]
plus=[]
cnt=Counter(a)
zerocnt=cnt[0]
minuscnt=0
pluscnt=0
for i in range(n):
    if a[i]<0:
        minuscnt+=1
        minus.append(a[i])
    elif a[i]>0:
        pluscnt+=1
        plus.append(a[i])


if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans%mod)
    quit()

if minuscnt==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=a[i]
            ans%=mod
        print(ans)
    else:
        for i in range(k):
            ans*=a[-1-i]
            ans%=mod
        print(ans)
    quit()

if minuscnt%2==1:
    minuscnt-=1


plus.reverse()




ans=1
nokori=k
m,p=0,0


while nokori:
    
    if m==minuscnt:
        if p!=pluscnt:
            ans*=plus[p]
            p+=1
            nokori-=1
        else:
            ans=0
            nokori=0
    elif p==pluscnt:
        if nokori==1:
            ans=0
            nokori-=1
        else:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
    elif p+1==pluscnt:
        if nokori%2==0:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
            
        else:
            ans*=plus[p]
            p+=1
            nokori-=1
            
            
            
            
            
            
            
            
    elif nokori==1:
        ans*=plus[p]
        nokori-=1
    elif plus[p]*plus[p+1]>minus[m]*minus[m+1]:
        
        
        
        
        
        ans*=plus[p]
        p+=1
        nokori-=1
    else:
        ans*=minus[m]*minus[m+1]
        m+=2
        nokori-=2
    ans%=mod
print(ans%mod)

Solution (Python):
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and [0,0] in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if [0,0] in A:
            print(0)
            sys.exit()
        for i in range(N):
            prod = prod * A[i][0] % MOD
        prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        for i in range(K):
            prod = prod * A[-1-i][0] % MOD
        prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif lastp == -1 or indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        for i in range(K):
            if A[indp][0] * A[lastp][0] > A[indn][0] * A[lastn][0]:
                if i == lastn:
                    prod = prod * A[indp][0] % MOD
                else: prod = prod * A[i][0] % MOD
            else:
                if i == lastp:
                    prod = prod * A[indn][0] % MOD
                else:
                    prod = prod * A[i][0] % MOD
    print(prod)

Solution (Python):
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if K==N:
    out=1
    for i in range(K):
        out = out*A[i]%p
    print(out)
elif Nminus==N and K%2==1:
    out=1
    for i in range(K):
        out = out*Aminus[N-i-1]%p
    print(out)
else:
    l=0
    r=0
    out=1
    inf = float('inf')
    while K>0:
        if l+1<=Nplus-1:
            cand1 = Aplus[l]*Aplus[l+1]
        elif l==Nplus-1:
            cand1 = Aplus[l]
        else:
            cand1 = -1*inf

        if r+1<=Nminus-1:
            cand2 = Aminus[r]*Aminus[r+1]
        elif r==Nminus-1:
            cand2 = Aminus[r]
        else:
            cand2 = -1*inf

        if cand1>cand2 or K==1:
            out=out*Aplus[l]%p
            K += -1
            l += 1
        else:
            out=out*Aminus[r]*Aminus[r+1]%p
            K += -2
            r += 2
    print(out)

Solution (Python):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N or N == K:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevpos = None
    prevneg = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and (nextneg is None or nextpos is None):
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()