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):
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=1
c=0
l=0
r=-1
c1=0
while True:
    if k-c>=2:
        if a[r]*a[r-1]>a[l]*a[l+1]:
            s*=a[r]*a[r-1]
            r-=2
            c+=2
        else:
            s*=a[l]*a[l+1]
            l+=2
            c+=2
    else:
        if a[r]<0:
            s=1
            a=np.absolute(a)
            a=list(a)
            a.sort()
            while True:
                s*=a[c1]
                c1+=1
                s%=10**9+7
                if c1==k:
                    s=-s
                    print(s%10**9+7)
                    exit()
        else:s*=a[r]
        c+=1
    s%=10**9+7
    if k==c:break
print(s)

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

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

alst.sort()

if n == k:
    ans = 1
    for num in alst:
        ans *= num
        ans %= MOD
    print(ans)
    exit()

if k == 1:
    print(alst[-1] % MOD)
    exit()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst = alst[::-1]
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True,key = lambda x:x[0])
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    elif blst[i][1] == 1:
        last_plus = blst[i][0]
    else:
        print(0)
        exit()
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    if blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if (flg_plus and flg_minus) or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus == k:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    elif minus_s == plus_s == 0:
        if next_minus == 0:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        else:
            print(0)
            exit()
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Solution (Python):
mod = 10**9 + 7
n, k, *A = map(int, open(0).read().split())
if k == n:
    s = 1
    for a in A[:k]:
        s *= a
        s %= mod
    print(s)
elif k % 2 == 1 and all(a <= 0 for a in A):
    A.sort(key=abs, reverse=1)
    s = A.pop() % mod
    c = 1
    while c < k:
        t = A.pop() * A.pop() % mod
        s *= t
        s %= mod
        c += 2
    print(s)
else:
    A.sort(key=abs)
    pos_A = [a for a in A if a >= 0]
    neg_A = [a for a in A if a <= 0]

    if k % 2 == 1:
        s = pos_A.pop()
        c = 1
    else:
        s = 1
        c = 0
    while c < k:
        if len(pos_A) >= 2 and len(neg_A) >= 2:
            if pos_A[-1] * pos_A[-2] > neg_A[-1] * neg_A[-2]:
                t = pos_A.pop() * pos_A.pop() % mod
            else:
                t = neg_A.pop() * neg_A.pop() % mod
        elif len(pos_A) < 2:
            t = neg_A.pop() * neg_A.pop() % mod
        else:
            t = pos_A.pop() * pos_A.pop() % mod
        s *= t
        s %= mod
        c += 2
    print(s)

Solution (Python):

def main():
    MOD = 10**9+7
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al_abs = []
    al_nl = []
    for a in al: 
        if a > 0: sig = 1
        elif a < 0 : 
            sig = -1
            al_nl.append(a)
        else: sig = 0
        al_abs.append((abs(a), sig))

    if n == k:
        ans = 1
        for i in range(k):
            a = al[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()

    al_abs.sort(reverse=True)
    n_cnt = 0
    last_p = -1
    last_n = -1
    for i in range(k):
        a, sig = al_abs[i]
        if sig == -1:
            n_cnt+=1
            last_n = i
        elif sig == 1:
            last_p = i
    
    ans = 1
    if n_cnt%2 == 0:
        for i in range(k):
            a, sig = al_abs[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    next_p = -1
    next_n = -1 
    for i in range(k,n):
        a, sig = al_abs[i]
        if sig == 1 and next_p == -1:
            next_p = i
        elif sig == -1 and next_n == -1:
            next_n = i
        if next_n != -1 and next_p != -1:
            break

    comp_np = 0
    if next_p != -1:
        last_n_val = al_abs[last_n][0]
        next_p_val = al_abs[next_p][0]
        comp_np = next_p_val*(1.0)/last_n_val

    comp_pn = 0
    if next_n != -1 and last_p != -1:
        last_p_val = al_abs[last_p][0]
        next_n_val = al_abs[next_n][0]
        comp_pn = next_n_val*(1.0)/last_p_val

    if comp_np == 0 and comp_pn > 0:
        np_or_pn = False
    elif comp_pn == 0 and comp_np > 0:
        np_or_pn = True
    elif comp_np > 0 and comp_pn > 0:
        if next_p_val*last_p_val > next_n_val*last_n_val:
            np_or_pn = True
        else:
            np_or_pn = False

    elif comp_np == 0 and comp_pn == 0:
        if 0 in al:
            print(0)
            exit()
        else:
            al_nl.sort(reverse=True)
            for i in range(k):
                a = al_nl[i]
                ans *= (a)
                ans %= MOD
            print(ans)
            exit()


    

    for i in range(k):
        if np_or_pn and i == last_n:
            continue
        if (not np_or_pn) and i == last_p:
            continue
        a, sig = al_abs[i]
        ans *= a
        ans %= MOD

    if np_or_pn:
        ans *= next_p_val
        ans %= MOD
    else:
        ans *= next_n_val
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
mod=10**9+7
def mull(a,b):
	return ((a%mod)*(b%mod))%mod
def maxProductSubarrayOfSizeK(A, n, k): 
  
    
    A.sort() 
  
    
    
    product = 1
  
    
    
    
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    
    
    
    
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product =mull(product,A[i]) 
        return product 
  
    
    
    i = 0
  
    
    j = n - 1
  
    
    
    
    
    
    
    if (k & 1): 
        product =mull(product,A[j]) 
        j-= 1
        k-=1
  
    
    
    
    
    
    
    k >>= 1
  
    
    
    for itr in range(k) : 
  
        
        left_product = A[i] * A[i + 1] 
  
        
        right_product = A[j] * A[j - 1] 
  
        
        
        
        if (left_product > right_product) : 
            product =mull(product,left_product) 
            i += 2
          
        else : 
            product=mull(product,right_product) 
            j -= 2
  
    
    return product 
def check(a):
	for i in a:
		if i>=0:
			return False 
	return True 
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
mod=10**9+7
ans=1 
if check(a):
	if k%2==0:
		a.sort()
		for i in a[:k]:
			ans=mull(ans,i+mod)  
	else:
		a.sort(reverse=True)
		for i in a[:k]: 
			ans=mull(ans,i+mod) 
	print(ans%mod)
else:
	print(maxProductSubarrayOfSizeK(a,n,k)%mod)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
d1, d2 = sorted([q for q in a if q > 0], reverse=True), sorted([q for q in a if q < 0])
C = 1000000007
if len(d1)+len(d2) < k:
    print(0)
elif k == n:
    ans = 1
    for q in a:
        ans = ans*q % C
    print(ans)
elif len(d1) == 0 and k % 2 == 0:
    ans = 1
    for q in range(k):
        ans = ans*d2[q] % C
    print(ans)
elif len(d1) == 0 and len(d2) < n:
    print(0)
elif len(d1) == 0:
    ans = 1
    for q in range(len(d2)-1, len(d2)-k-1, -1):
        ans = ans*d2[q] % C
    print(ans)
elif len(d2) == 0:
    ans = 1
    for q in range(k):
        ans = ans*d1[q] % C
    print(ans)
else:
    ind = 0
    ans, now, w = 0, 0, min(k+1, len(d2)+1)
    for q in range(max(0, (k-len(d1)+1)//2*2), w, 2):
        if now == 0:
            """now = 1
            for q1 in range(q):
                now *= d2[q1]
            for q1 in range(k-q):
                now *= d1[q1]
            ans = now"""
            now, ind = 1, q
        else:
            if d1[k-q+1]*d1[k-q] <= d2[q-2]*d2[q-1]:
                ind = q
    ans = 1
    for q in range(ind):
        ans = ans*d2[q] % C
    for q in range(k-ind):
        ans = ans*d1[q] % C
    print(ans)

Solution (Python):
MOD = 1000000007

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

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

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1
sign = 1

for i in range(K):
    res *= A[~i]
    res %= MOD
    if A[~i] < 0:
        sign *= -1

    if A[~i] == 0:
        sign = 0

if sign == 1:
    print(res % MOD)

elif sign == 0:
    print(0)

else:
    flag1 = False
    tmp1 = -1
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            flag1 = True
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 /= A[minneg]
    flag2 = False
    tmp2 = -1
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        flag2 = True
        tmp2 *= A[maxneg]
        tmp2 /= A[minpos]
    if flag1 and flag2:
        if A[maxpos] * A[minpos] > A[maxneg] * A[minneg]:
            print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
        else:
            print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    elif flag1:
        print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
    elif flag2:
        print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
                res %= MOD
            print(res % MOD)

Solution (Python):
N,K = map(int,input().split())
A = [int(a) for a in input().split()]
Ap, Am, A0 = [],[],[]
for a in A:
    if a>0: Ap.append(a)
    elif a<0 : Am.append(a)
    else: A0.append(a)
mod = 10**9+7

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

if len(Ap)==0 and K%2==1:
    if len(A0)==0:
        A.sort()
        A.reverse()
        for i in range(K):
            ans = (ans*A[i])%mod
        print(ans)
        exit()
    else:
        print(0)
        exit()

Ap.sort()
Ap.reverse()
Am.sort()
if K%2==1:
    ans = Ap[0]
    Ap = Ap[1:]
    K -= 1

if K > len(Ap)+len(Am):
    print(0)
    exit()
if K == len(Ap)+len(Am) and len(Am)%2==1:
    print(0)
    exit()

Apair = [Ap[i]*Ap[i+1] for i in range(0,len(Ap)-1,2)]
for i in range(0,len(Am)-1,2):
    Apair.append(Am[i]*Am[i+1])
Apair.sort()
Apair.reverse()
for i in range(K//2):
    ans = (ans*Apair[i])%mod
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n, k = map(int, input().split())
a = [int(item) for item in input().split()]

if n == k:
    ans = 1
    for item in a:
        ans *= item
        ans %= MOD
    print(ans % MOD)
    exit()
plus = 0; minus = 0; zero = 0
p = []; m = []
for item in a:
    if item > 0:
        plus += 1
        p.append(item)
    elif item == 0:
        zero += 1
    else:
        minus += 1
        m.append(-item)
p.sort()
m.sort()

if plus == 0:
    if k % 2 == 0:
        if minus >= k:
            ans = 1
            for i in range(k):
                ans *= m.pop()
                ans %= MOD
            print(ans)
            exit()
        else:
            print(0)
            exit()
    else:
        if zero:
            print(0)
            exit()
        ans = 1
        for item in m[:k]:
            ans *= -item
            ans %= MOD
        print(ans % MOD)
        exit()
if minus == 0:
    if plus >= k:
        ans = 1
        for i in range(k):
            ans *= p.pop()
            ans %= MOD
        print(ans % MOD)
        exit()
    else:
        print(0)
        exit()


if k <= (minus // 2) * 2 + plus:
    if k % 2 == 0:
        ans = 1
    else:
        ans = p.pop()
        k -= 1
    for i in range(k // 2):
        pval = 0; mval = 0
        if len(p) > 1:
            pval = p[-1] * p[-2]
        if len(m) > 1:
            mval = m[-1] * m[-2]
        if pval > mval:
            p.pop(); p.pop()
            ans *= pval
            ans %= MOD
        else:
            m.pop(); m.pop()
            ans *= mval
            ans %= MOD
    print(ans % MOD)
    exit()

else:
    if zero > 0:
        print(0)
        exit()
    else:
        
        exit()

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):
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= mod
    print(ans)
    exit()
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
tmp_ = -1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        num = i
        F = True
    else:
        tmp_ = tmp
        num = i
        break

if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            ans *= a
            ans %= mod
            if i == K-1:
                print(ans)
                exit()
    else:
        B.sort(reverse=True)
        K //= 2
        for i, b in enumerate(B):
            ans *= b
            ans %= mod
            if i == K-1:
                print(ans)
                exit()
A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    if F:
        print(0)
        exit()
    else:
        ans *= tmp_

B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans % mod)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

if max(a) < 0:
    a.sort()
    ans = 1
    if k % 2 == 0:
        for e in a[:k]:
            ans *= e
            ans %= mod
    else:
        for e in a[-k:]:
            ans *= e
            ans %= mod

    print(ans)

elif k == n:
    ans = 1
    for e in a:
        ans *= e
        ans %= mod

    print(ans)

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

    neg.sort()
    pos.sort(reverse=True)

    ans = 1
    if k % 2:
        ans *= pos.pop(0)
        k -= 1

    nums = [e1 * e2 for e1, e2 in zip(neg[::2], neg[1::2])]
    nums += [e1 * e2 for e1, e2 in zip(pos[::2], pos[1::2])]

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

    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N, K = na()
a_array = na()

mod = 10 ** 9 + 7

aa = []

for a in a_array:
    if a >= 0:
        aa.append([a, 1])
    else:
        aa.append([abs(a), 0])

aa = sorted(aa, key=lambda x: - (x[0]+0.1*x[1]))

minus_count = 0

last_plus = [0, 0]
last_minus = [0, 0]

for i in range(K):
    v, f = aa[i]
    if f == 0:
        minus_count += 1
        last_minus = [v, i]
    else:
        last_plus = [v, i]

ans = 1

if minus_count % 2 == 0:
    for i in range(K):
        ans = (ans * aa[i][0]) % mod
    print(ans)
    exit()
else:
    if aa[K-1][0] == 0:
        print(0)
        exit()
    plus_ok = 0
    minus_ok = 0
    change_plus = [-1, 0]
    change_minus = [0, 0]
    for i in range(K, N):
        v, f = aa[i]
        if plus_ok == 0 and minus_count != 0 and f == 1:
            plus_ok = 1
            change_plus = [v, i]
        elif minus_ok == 0 and minus_count != K and f == 0:
            minus_ok = 1
            change_minus = [v, i]
        if minus_ok == 1 and plus_ok == 1:
            break

    if minus_ok == 0 and plus_ok == 0:
        for i in range(N-1, N-K-1, -1):
            ans = (ans * aa[i][0]) % mod
        if ans == 0:
            print(0)
        else:
            print(mod - ans)
        exit()

    D = last_plus[0] * change_plus[0] - last_minus[0] * change_minus[0]

    

    ans = 1

    if D >= 0:
        for i in range(K):
            if i != last_minus[1]:
                ans = (ans * aa[i][0]) % mod
        ans = ans * aa[change_plus[1]][0] % mod
        print(ans)
    else:
        for i in range(K):
            if i != last_plus[1]:
                ans = (ans * aa[i][0]) % mod
        ans = ans * aa[change_minus[1]][0] % mod
        print(ans)

Solution (Python):
import numpy as np

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

al_pr = sorted(al_pr)

al = al_pr

al_pr = np.array(al_pr)

neg_num = int(np.sum(al_pr < 0))
pos_num = int(np.sum(al_pr > 0))
zero_num = int(np.sum(al_pr == 0))

mod = 10**9+7

f1 = (k % 2 == 1 and max((k-1 - (neg_num // 2)*2), 0) + 1 <= pos_num)
f2 = (k % 2 == 0 and max(k - (neg_num // 2)*2, 0) <= pos_num)

if f1 or f2:
    done = 0
    right = -1
    left = 0
    ans = 1
    while done < k:
        if k - done == 1:
            ans *= al[right]
            ans %= mod
            done += 1
        else:
            if al[right-1] > 0:
                cand1 = al[right] * al[right-1]
            else:
                cand1 = 0
            if al[left+1] < 0:
                cand2 = al[left] * al[left+1]
            else:
                cand2 = 0
            if cand1 > cand2:
                ans *= cand1
                ans %= mod
                right -= 2
            else:
                ans *= cand2
                ans %= mod
                left += 2
            done += 2
elif zero_num > 0:
    ans = 0
elif pos_num == 0:
    ans = 1
    for i in range(k):
        ans *= al[neg_num-1-i]
        ans %= mod
else:
    ans = 1
    for i in range(k):
        ans *= al[i]
        ans %= mod

print(ans)

Solution (Python):
MOD = int(1e9+7)
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
flag = 0
for a in A:
    if a>0:
        flag = 1
        break
if N==K:
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)


elif flag == 0 and K%2==1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)

else:
    A = sorted(A, key=abs, reverse = True)
    last_pos = -1
    last_neg = -1
    count_neg = 0
    is_zero = 0
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
        if A[i]>0:
            last_pos = i
        elif A[i]<0:
            last_neg = i
            count_neg += 1
        else:
            is_zero = 1
            break
    if is_zero == 1:
        print(0)
    elif count_neg%2 == 0:
        print(ans)
    else:
        flag_pos = 0
        flag_neg = 0
        new_pos = -1
        new_neg = -1
        for i in range(K,N):
            if A[i]>0 and flag_pos==0:
                flag_pos = 1
                new_pos = i
            elif A[i]<0 and flag_neg==0:
                flag_neg = 1
                new_neg = i
            if flag_pos == 1 and flag_neg == 1:
                break

        if last_pos > -1 and last_neg > -1 and new_pos > -1 and new_neg > -1:
            f1 = A[new_pos] * A[last_pos]
            f2 = A[new_neg] * A[last_neg]
            if f1>f2:
                ans = 1
                for i in range(K):
                    if i != last_neg:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_pos]) % MOD
            else:
                ans = 1
                for i in range(K):
                    if i != last_pos:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_neg]) % MOD
        elif last_pos > -1 and new_neg > -1:
            ans = 1
            for i in range(K):
                if i != last_pos:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_neg]) % MOD
        elif last_neg > -1 and new_pos > -1:
            ans = 1
            for i in range(K):
                if i != last_neg:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_pos]) % MOD
        else:
            ans = 0
            
        print(ans)

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

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

    A.sort(key=abs, reverse=True)

    ans = 1
    sgn = 1

    lm, lp = None, None
    for i, x in enumerate(A[:K]):
        if x < 0:
            sgn = -sgn
            lm = x
        else:
            lp = x
        ans = ans * x % MOD

    if K == N or sgn == 1 or ans == 0:
        print(ans)
        return

    fm, fp, z = None, None, False
    for i, x in enumerate(A[K:]):
        if x < 0:
            if fm is None:
                fm = x
        elif x == 0:
            z = True
        else:
            if fp is None:
                fp = x

    
    if lp is None:
        
        if fp is not None:
            ans = ((ans * pow(lm, MOD - 2, MOD)) % MOD) * fp % MOD
            print(ans)
            return

        if z:
            print(0)
            return

        A.sort(key=abs)
        ans = 1
        for i, x in enumerate(A[:K]):
            ans = ans * x % MOD
        print(ans)
        return

    else:
        if fp is not None and fm is not None:
            if fm * lm >= fp * lp:
                ans = ((ans * pow(lp, MOD - 2, MOD)) % MOD) * fm % MOD
                print(ans % MOD)
                return
            else:
                ans = ((ans * pow(lm, MOD - 2, MOD)) % MOD) * fp % MOD
                print(ans % MOD)
                return

        if fp is not None:
            ans = ((ans * pow(lm, MOD - 2, MOD)) % MOD) * fp % MOD
            print(ans)
            return

        if fm is not None:
            ans = ((ans * pow(lp, MOD - 2, MOD)) % MOD) * fm % MOD
            print(ans)
            return


if __name__ == '__main__':
    main()

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

mod = 10**9+7
def _ans(_a):
    ret = _a[0]
    for _aa in _a[1:]:
        ret = (ret*_aa)%mod
    return ret


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

if len(a) == k:
    print(_ans(a))
    exit(0)

ap = [aa for aa in a if aa > 0]
an = [aa for aa in a if aa < 0]
apl, anl = len(ap), len(an)


if apl + anl < k:
    print(0)
    exit(0)

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


if apl == 0:
    if k % 2 == 1:
        if apl + anl < n:
            print(0)
            exit(0)
        an = an[::-1]
    print(_ans(an[:k]))
    exit(0)


ans = 1
api, ani = 0, 0
if k % 2 == 1:
    ans = ap[0]
    api += 1
    k -= 1

while k > 0:
    if apl - api < 2:
        while k > 0:
            ans = (ans * an[ani] * an[ani+1]) % mod
            ani += 2
            k -= 2
        break
    if anl - ani < 2:
        while k > 0:
            ans = (ans * ap[api] * ap[api+1]) % mod
            api += 2
            k -= 2
        break

    app = ap[api] * ap[api+1]
    ann = an[ani] * an[ani+1]
    if app > ann:
        ans = (ans * app) % mod
        api += 2
    else:
        ans = (ans * ann) % mod
        ani += 2
    k -= 2

print(ans)

Solution (Python):
N,K = map(int,input().split())
MOD = 10**9 + 7
A = list(map(int,input().split()))
Ap = [a for a in A if a >= 0]
An = [-a for a in A if a < 0]
Ap.sort()
Ap.reverse()
An.sort()
An.reverse()

if len(Ap) == 0 and K % 2 == 1:
	ans = 1
	An.reverse()
	for i in range(K):
		ans = (ans * -An[i]) % MOD
	print(ans)
	exit()

B = [(a, 1) if a >= 0 else (-a, -1) for a in A]
B.sort()
B.reverse()
M = [0 if B[0][1] > 0 else 1]
for i in range(1, N):
	M.append(M[i-1] + (0 if B[i][1] > 0 else 1))

i = K-1
if M[i] % 2 == 0 or K == N:
	ans = 1
	v = 1 if (M[i] % 2 == 0) else -1
	for j in range(K):
		ans = (ans * B[j][0]) % MOD
	print((ans * v) % MOD)
else:
	n = M[i]
	p = K - n
	if len(An) == n or p == 0:
		n -= 1
		p += 1
	elif len(Ap) == p:
		n += 1
		p -= 1
	elif Ap[p-1] * Ap[p] >= An[n-1] * An[n]:
		n -= 1
		p += 1
	else:
		n += 1
		p -= 1
	ans = 1
	for i in range(p):
		ans = (ans * Ap[i]) % MOD
	for i in range(n):
		ans = (ans * An[i]) % MOD
	print(ans)

Solution (Python):
import itertools
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq

MOD = 10 ** 9 + 7


def solve(N, K, As):
    originalK = K
    
    minus = [a for a in As if a < 0]
    minus.sort(reverse=True)
    zero = [a for a in As if a == 0]
    plus = [a for a in As if a > 0]
    plus.sort()

    if len(zero) and len(zero) > N - K:
        return 0

    ans = 1
    while K >= 2 and (len(plus) >= 2 or len(minus) >= 2):
        p1 = -1
        p2 = -1
        m = -1
        if len(plus) >= 1:
            p1 = plus[-1]
        if len(plus) >= 2:
            p2 = plus[-1] * plus[-2]
        if len(minus) >= 2:
            m = minus[-1] * minus[-2]

        if m >= p2:
            ans *= (m % MOD)
            ans %= MOD
            minus.pop()
            minus.pop()
            K -= 2
        else:
            ans *= (p1 % MOD)
            ans %= MOD
            plus.pop()
            K -= 1

    while K > 0:
        if len(plus):
            ans *= plus.pop()
            ans %= MOD
        else:
            ans *= minus.pop(0)
        K -= 1
    if ans < 0 and zero:
        return 0
    if ans < 0:
        minus = [a for a in As if a < 0]
        plus = [a for a in As if a > 0]
        minus.sort()
        plus.sort(reverse=True)
        ans = 1
        for _ in range(originalK):
            if plus and minus:
                if abs(plus[-1]) < abs(minus[-1]):
                    ans *= plus.pop()
                else:
                    ans *= minus.pop()
            elif plus:
                ans *= plus.pop()
            else:
                ans *= minus.pop()
            ans %= MOD
        ans %= MOD

    return ans


def slowsolve(N, K, As):
    ans = -10 ** 9
    for p in itertools.combinations(As, K):
        k = 1
        for i in p:
            k *= i
        ans = max(ans, k)
    return ans
























def rand(N, a, b):
    import random
    return [random.randint(a, b) for _ in range(N)]





















if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Solution (Python):
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)
import time
l=[]
if K%2==0 or (K%2==1 and A[0]>=0):
  for i in range(K//2):
    if d[0]*d[1]>d[-1]*d[-2] and (i==K//2-1 or (len(d)>2 and  d[2]>0)):
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
  ans%=10**9+7
print(ans)