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):
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
    exit()

while k > 0:
    if k == 1 or len(mia) <= 1:
        if len(pla) == 0:
            cnt *= mia.pop()
        elif len(pla) > 0:
            cnt *= pla.pop()
        k -= 1
    elif len(pla) <= 1:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    elif pla[-1] * pla[-2] > mia[-1] * mia[-2]:
        cnt *= pla.pop()
        k -= 1
    elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    cnt %= mod
else:
    print(cnt)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9 + 7
c = 0
z = 0
for i in a:
    if i < 0:
        c += 1
    elif i == 0:
        z += 1
if c == n and k & 1:
    a.reverse()
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(-ans % mod)
elif c == n:
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(ans)
elif k == n:
    for i in a:
        ans *= abs(i)
        ans %= mod
    print(((-1)**(c & 1) * ans) % mod)
else:
    plus = [i for i in a if i > 0]
    minus = [i for i in a if i <= 0]
    plus.sort(reverse=1)
    minus.sort()
    plus += [0] * z
    x = len(plus)
    y = len(minus)
    p, m = 0, 0
    if k & 1:
        ans *= plus[0]
        p += 1
    for i in range(k // 2):
        if x - 1 <= p:
            ans *= minus[m] * minus[m + 1]
            m += 2
        elif y - 1 <= m:
            ans *= plus[p] * plus[p + 1]
            p += 2
        else:
            if minus[m] * minus[m + 1] >= plus[p] * plus[p + 1]:
                ans *= minus[m] * minus[m + 1]
                m += 2
            else:
                ans *= plus[p] * plus[p + 1]
                p += 2
        ans %= mod

    print(ans % mod)

Solution (Python):





import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans % modVal)
        return
    
    
    if max(nums) < 0:
        nums.sort()
        ans = 1
        
        if k % 2:
            for i in range(k):
                ans *= nums[-i - 1] % modVal
                ans %= modVal
        
        else:
            for i in range(k):
                ans *= nums[i] % modVal
                ans %= modVal
        print(ans % modVal)
        return
    
    
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()  
    
    
    if len(absNums) < k:
        print(0)
        return

    
    posOverK = []
    negOverK = []
    posLessK = []
    negLessK = []
    for _ in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])

    posOverK.sort()
    negOverK.sort()
    posLessK.sort()
    negLessK.sort()
    
    
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        maxNeg = None
        maxPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]
        if posLessK:
            maxPos = posLessK[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            
            if maxPos * minPos > maxNeg * minNeg:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        
        elif not (minNeg and maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and not (minPos and maxNeg):
            negOverK[0] = maxPos
        
        elif zeroCnt > 0:
            print(0)
            return
    
    
    ans = 1
    for i in posOverK:
        ans *= i % modVal
        ans = ans % modVal
    for i in negOverK:
        ans *= i % modVal
        ans = ans % modVal
    
    print(ans % modVal)
    return

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

ans = 1
B = deque(A)

if K % 2 == 1:
    ans *= B.popleft()

for _ in range(K // 2):
    l = B[0] * B[1]
    r = B[-1] * B[-2]
    if l >= r:
        ans *= B.popleft() * B.popleft()
    else:
        ans *= B.pop() * B.pop()
    if ans > 0: ans %= MOD
    else: ans = (ans % MOD) - MOD

if ans < 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD

print(ans % MOD)

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]

for i in range(n):
    if arr[i]>0:
        cnt_plus+=1
        arr_plus.append(arr[i])
    elif arr[i]<0:
        cnt_minus+=1
        arr_minus.append(-arr[i])
    else:
        cnt_zero+=1
if cnt_plus+cnt_minus<k: 
    print(0)
    exit()
    
if k==n: 
    if cnt_zero!=0: 
        print(0)
    else:
        ans=1
        for i in range(cnt_plus):
            ans*=arr_plus[i]
            ans%=mod
        for i in range(cnt_minus):
            ans*=arr_minus[i]
            ans%=mod
        if cnt_minus%2==0: 
            print(ans)
        else: 
            print((-ans)%mod)
    exit()
if cnt_plus==0 and k%2==1: 
    if cnt_zero!=0: 
        print(0)
    else: 
        arr_minus=sorted(arr_minus)
        tmp=1
        for i in range(k):
            tmp*=arr_minus[i]
            tmp%=mod
        print((-tmp)%mod)
    exit()
else: 
    arr_plus=sorted(arr_plus,reverse=True)
    arr_minus=sorted(arr_minus,reverse=True)
    if k%2==0: 
        ans=1
        pos_plus=0
        pos_minus=0
        cnt=0
    else: 
        ans=arr_plus[0]
        pos_plus=1
        pos_minus=0
        cnt=1
    while cnt<k:
        cand1=0
        if pos_plus<=cnt_plus-2: 
            cand1=arr_plus[pos_plus]*arr_plus[pos_plus+1]      
            cand2=0
        if pos_minus<=cnt_minus-2: 
            cand2=arr_minus[pos_minus]*arr_minus[pos_minus+1]
        if cand1>=cand2: 
            pos_plus+=2
            ans*=cand1
            ans%=mod
        else: 
            pos_minus+=2
            ans*=cand2
            ans%=mod
        cnt+=2
    print(ans)
    exit()

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

ans=1
mod=10**9+7

a.sort()
if a[0]>=0:
    for i in range(n-1,n-k-1,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
if a[-1]<=0:
    if k%2:
        for i in range(n-1,n-k-1,-1):
            ans*=a[i]
            ans%=mod
    else:
        for i in range(k):
            ans*=a[i]
            ans%=mod
    print(ans)
    exit()
l=0;r=n-1
if k%2:
    ans=a[-1]
    r-=1
    k-=1
while k:
    if a[l]*a[l+1]>a[r]*a[r-1]:
        ans*=a[l]*a[l+1]
        l+=2
    else:
        ans*=a[r]*a[r-1]
        r-=2
    k-=2
    ans%=mod
   
print(ans)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==1:
    ans=ans*a[j]%mod

if a[-1]<0 and k%2==1:
    ans=1
    for i in a[n-k:]:
        ans=ans*i%mod
print(ans)

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

mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)




n_min = k - (max(n - len(negs), 0))

n_max = min(n, k)


if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= -negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= -negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1

    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0

while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= -negs[n_idx]
        n_idx += 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= -negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1


if neg_cnt % 2 == 0 or n == k:
    
    print(ans % mod)
    exit()
else:
    
    

    
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(-negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= -negs[n_idx]
        ans %= mod
    else:
        
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(-negs[n_idx - 1])
            ans %= mod
        else:
            ans *= -negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)
    exit()

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

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0


        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2
else:
    hugo = 1

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        if tmp % 2 == 1:
            tmp -= 1
            pl_num += 1
            tmp_ans = a[n-1]
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 0
                tmp_m_seki = 0
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                elif tmp_p_seki == 0 and tmp_m_seki == 0:
                    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            
            
            
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Solution (Python):

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

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1

    if minus_counter%2 == 1:
        
        if minus_now >= len(minuss) or plus_now == 0:
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        elif plus_now >= len(pluss) or minus_now == 0:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod
        
        elif pluss[plus_now]*pluss[plus_now-1] > -minuss[minus_now]*(-minuss[minus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = 10000000000000  
        
        if plus_target <= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
    answer = answer * -1
print(answer%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return
    
    if all(a < 0 for a in A) and K%2 == 1:
        A.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return
    
    A.sort(key = abs,reverse = True)
    cnt_m = 0
    ans = 1
    last_p = -1
    last_m = 1
    for i in range(K):
        if A[i] == 0:
            print(0)
            return
        elif A[i] < 0:
            ans *= A[i]
            ans %= MOD
            cnt_m += 1
            last_m = A[i]
        else:
            ans *= A[i]
            ans %= MOD
            last_p = A[i]
    if cnt_m%2 == 0:
        print(ans)
    else:
        diff1 = last_p
        diff2 = last_m
        inv1 = pow(last_m,MOD - 2,MOD)
        inv2 = pow(last_p,MOD - 2,MOD)
        for i in range(K,N):
            if A[i] >= 0:
                diff1 *= A[i]
                inv1 *= A[i]
                inv1 %= MOD
                break
            if i == N - 1:
                diff1 = -1
        for i in range(K,N):
            if A[i] < 0:
                diff2 *= A[i]
                inv2 *= A[i]
                inv2 %= MOD
                break
            if i == N - 1:
                diff2 = -1
        
        if last_p > 0:
            if diff1 < diff2:
                ans *= inv2
                ans %= MOD
            else:
                ans *= inv1
                ans %= MOD
        else:
            ans *= inv1
            ans %= MOD
        print(ans)
if __name__ == '__main__':
    main()

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
    exit()

while k > 0:
    if k == 1 or len(mia) <= 1:
        if len(pla) == 0:
            cnt *= mia.pop()
        elif len(pla) > 0:
            cnt *= pla.pop()
        k -= 1
    elif len(pla) <= 1:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    elif pla[-1] * pla[-2] > mia[-1] * mia[-2]:
        cnt *= pla.pop()
        k -= 1
    elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    cnt %= mod
else:
    print(cnt)

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num, cnt = 1, [], 0

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
        cnt += 1
    num.append(tmp)
    ans = ans * tmp % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    pos = []
    neg = []
    zero = []
    for v in a:
        if v == 0:
            zero.append(v)
        elif 0 < v:
            pos.append(v)
        else:
            neg.append(v)
    if len(pos) + len(neg) < k:
        print(0)
    else:
        if k%2 == 0:
            if len(pos) + len(neg) == k and len(pos) % 2 == 1:
                if len(zero) > 0:
                    print(0)
                else:
                    ans = 1
                    for v in pos:
                        ans *= v
                        ans %= MOD
                    for v in neg:
                        ans *= v
                        ans %= MOD
                    print(ans % MOD)
            else:
                pos.sort(reverse=True)
                neg.sort()
                ans = 1
                p, q = 0, 0
                while k > 0:
                    if p+1 < len(pos) and q+1 < len(neg):
                        x, y = pos[p]*pos[p+1], neg[q]*neg[q+1]
                        if x > y:
                            ans *= x
                            p += 2
                        else:
                            ans *= y
                            q += 2
                    elif p+1 < len(pos):
                        ans *= pos[p]*pos[p+1]
                        p += 2
                    else:
                        ans *= neg[q]*neg[q+1]
                        q += 2
                    k -= 2
                    ans %= MOD
                print(ans % MOD)
        else:
            if 0 == len(pos):
                if 0 < len(zero):
                    print(0)
                else:
                    neg.sort(reverse=True)
                    ans = 1
                    for i in range(k):
                        ans *= neg[i]
                        ans %= MOD
                    print(ans)
            else:
                pos.sort(reverse=True)
                neg.sort()
                ans = pos[0]
                p, q = 1, 0
                k -= 1
                while k > 0:
                    if p+1 < len(pos) and q+1 < len(neg):
                        x, y = pos[p]*pos[p+1], neg[q]*neg[q+1]
                        if x > y:
                            ans *= x
                            p += 2
                        else:
                            ans *= y
                            q += 2
                    elif p+1 < len(pos):
                        ans *= pos[p]*pos[p+1]
                        p += 2
                    else:
                        ans *= neg[q]*neg[q+1]
                        q += 2
                    k -= 2
                    ans %= MOD
                print(ans % MOD)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

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

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
if max(a)<0:
  if k%2:a.sort(reverse=1)
  else:a.sort()
  ans=1
  for i in a[:k]:ans=(ans*i)%mod
  exit(print(ans))
if n==k:
  ans=1
  for i in a:ans=(ans*i)%mod
  exit(print(ans))
p=[(0,0)]
m=[(0,0)]
for i in a:
  if i<0:m.append((-i,1))
  else:p.append((i,0))
pp=mm=None
p.sort()
m.sort()
oe=0
ans=1
for i in range(k):
  if p[-1][0]>m[-1][0]:
    t,f=p.pop()
    pp=t
  else:
    t,f=m.pop()
    mm=t
  ans=(ans*t)%mod
  if ans==0:exit(print(0))
  oe^=f
if oe:
  if mm==None:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
  elif pp==None:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  elif pp*p[-1][0]>mm*m[-1][0]:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  else:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k==n:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k==1:
    print(a[-1])
    exit(0)
if k%2==1:
    rem = pa[-1]
    pa = pa[:-1]
na += [0]*n
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if i==k//2-1 and k%2==1:
        break
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= max(pa[pn]*pa[pn+1]*max(pa[pn+2], rem), na[nn]*na[nn+1]*max(pa[pn], rem))
print(ans%mod)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    plus = []
    minus = []
    for a in A:
        if a >= 0:
            plus.append(a)
        else:
            minus.append(a)
    
    flag = False
    if len(plus) > 0:
        if N == K:
            flag = (len(minus) % 2) == 0
        if N > K:
            flag = True
    elif len(plus) == 0:
        flag = (K % 2) == 0
    
    MOD = 10 ** 9 + 7
    ans = 1
    if flag:
        plus.sort(reverse=True)
        minus.sort()
        if K % 2 == 1:
            ans = plus.pop(0)
        B = []
        for i in range(0,len(plus),2):
            if i + 1 < len(plus):
                B.append(plus[i]*plus[i+1])
        for i in range(0,len(minus),2):
            if i + 1 < len(minus):
                B.append(minus[i]*minus[i+1])
        B.sort(reverse=True)
        for j in range(K//2):
            ans *= B[j]
            ans %= MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD

    print(ans)
        


if __name__ == "__main__":
    main()

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num, cnt = 1, [], 0

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
        cnt += 1
    num.append(tmp)
    ans = ans * tmp % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
    num.append(tmp)
    ans = ans * tmp % mod

cnt = sum(i < 0 for i in num)
if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Solution (Python):
from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

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

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or(len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)