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 sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]
 
for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)
 
B.sort(reverse=True)
C.sort(reverse=True)
 
if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod
 
    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()
 
if K>len(B)+len(C):
    print(0)
    sys.exit()
 
if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    elif Z==[] and K%2==1:
        ANS=1
        C.reverse()
        for i in range(K):
            ANS=ANS*(-C[i])%mod
        print(ANS)
        
    elif K%2==1:
        print(0)
        
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

Solution (Python):
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]
 
for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)
 
B.sort(reverse=True)
C.sort(reverse=True)
 
if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod
 
    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()
 
if K>len(B)+len(C):
    print(0)
    sys.exit()
 
if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    elif Z==[] and K%2==1:
        ANS=1
        C.reverse()
        for i in range(K):
            ANS=ANS*(-C[i])%mod
        print(ANS)
        
    elif K%2==1:
        print(0)
        
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

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

pi = 1
ni = 0
ans = 1
i = 0
while i < K-1:
  if A[ni]*A[ni+1] > A[-pi]*A[-pi-1]:
    ans = ans*A[ni]*A[ni+1]%mod
    ni += 2
    i += 2
    
  else:
    ans = ans*A[-pi]%mod
    pi += 1
    i += 1
    
if i == K-1:
  ans = ans*A[-pi]%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()))

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7
nm = 0
np = 0

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    else:
        if ai < 0 and nm == 0:
            nm = ai
        if ai > 0 and np == 0:
            np = ai
    if ai > 0:
        cp += 1

ans = 1
f = 0


if cnt % 2 and k < n:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) 
    else:
        cnt = 0
        f1 = 0
        f2 = 0
        for i, ai in enumerate(a):
            if f1 + f2 + cnt == k:
                break 
            if i == im:
                f1 = 1
                continue
            if i == ip:
                f2 = 1
                continue
            if f1 and ai <= 0:
                continue
            if f2 and ai >= 0:
                continue
            ans *= ai
            ans %= mod
            cnt += 1
        if ip == -1:
            ans *= np
        else:
            ans *= max(a[ip] * np, a[im] * nm)
        ans %= mod
        print(ans) 
        
else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= ai
        ans %= mod
    print(ans)

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%mod
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%mod
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%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 = sorted([int(a) for a in input().split()], key = lambda x: -abs(x))
P = 10 ** 9 + 7
m = 0
ans = 1
lp = 0
lm = 0
np = 0
nm = 0
for a in A[:K]:
    if a > 0:
        lp = a
        ans = ans * a % P
    elif a < 0:
        lm = a
        m ^= 1
        ans = ans * a % P
    else:
        print(0)
        exit()

if m == 0:
    print(ans)
    exit()

for a in A[K:]:
    if a > 0:
        np = a
        break
for a in A[K:]:
    if a < 0:
        nm = a
        break

if lp and nm and lm and np:
    if lp * np > lm * nm:
        print(ans * pow(lm, P-2, P) * np % P)
    else:
        print(ans * pow(lp, P-2, P) * nm % P)
elif lp and nm:
    print(ans * pow(lp, P-2, P) * nm % P)
elif lm and np:
    print(ans * pow(lm, P-2, P) * np % P)
else:
    A = A[::-1][:K]
    ans = 1
    for a in A:
        ans = ans * a % P
    print(ans)

Solution (Python):
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]


if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

if len(minus)==0:
    ans=1
    for i in range(K):
        ans*=plus[i]
        ans%=p
    print(ans)
    exit()

midx=0
pidx=0
ans=1

while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        if K>=2:
            nexmin=minus[midx]*minus[midx+1]
        else:
            nexmin=minus[midx]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
        fact=nexplus
    elif pidx>=len(plus):
        nexplus=-float("INF")
        fact=nexplus
    else:
        
        
        
        
        if K>=2:
            nexplus=plus[pidx]*plus[pidx+1]
        else:
            nexplus=plus[pidx]
        fact=plus[pidx]

    if nexmin>=nexplus:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=fact
        ans%=p
        pidx+=1
        K-=1


print(ans)

Solution (Python):
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%p
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%p
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)

Solution (Python):
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%p
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%p
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

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

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

A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if len(A_pos) == 0:
    if K % 2 == 1:
        A_neg.sort(reverse=True)
    else:
        A_neg.sort()
    ans = 1
    for a in A_neg[:K]:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos.sort()
A_neg.sort(reverse=True)
ans = 1
r = K
if r % 2 == 1:
    ans = ans * A_pos.pop() % MOD
    r -= 1

while r > 0:
    if len(A_pos) <= 1:
        ans = ans * A_neg.pop() * A_neg.pop() % MOD
    elif len(A_neg) <= 1:
        ans = ans * A_pos.pop() * A_pos.pop() % MOD

    else:
        acc_pos = A_pos[-1] * A_pos[-2]
        acc_neg = A_neg[-1] * A_neg[-2]

        if acc_pos > acc_neg:
            ans = ans * A_pos.pop() * A_pos.pop() % MOD
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % MOD
    r -= 2
print(ans % MOD)

Solution (Python):
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
index_change = 0
ans = 1
for i in range(n-1):
    if a[i] <= 0 and a[i+1] > 0:
        index_change = i+1
        break
else:
    if k % 2 == 1:
        for i in range(1, k+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
while k > 0:
    if k == 1:
        if r >= index_change:
            ans *= a[r]
            ans %= mod
            break
        else:
            ans *= a[l]*a[l+1]
            ans %= mod
            ans *= pow(a[r+1], mod-2, mod)
            ans %= mod
            break
    else:
        left = a[l]*a[l+1]
        right = a[r]*a[r-1]
        if left >= right:
            ans *= left
            ans %= mod
            l += 2
            k -= 2
        else:
            ans *= a[r]
            ans %= mod
            r -= 1
            k -= 1
print(ans)

Solution (Python):
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


if k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
elif neg_cnt == n and k % 2 == 1:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[v]), reverse=True)
    pos.sort(key=lambda v: abs(arr[v]), reverse=True)


    if k % 2:
        res = arr[pos[0]]
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    while i + j < k:
        res *= arr[pos[i]]
        i += 1
        res %= modulo

    print(res)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []

for Ai in A:
    if Ai>=0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(p)==0 and K%2==1:
    if 0 in A:
        print(0)
    else:
        n.sort(reverse=True)
        ans = 1
        
        for ni in n[:K]:
            ans *= ni
            ans %= MOD
        
        print(ans)
    exit()
    
if K==N:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()

if K%2==0:
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])

    l.sort(key=lambda x: abs(x), reverse=True)
    ans = 1
    
    for i in range(K//2):
        ans *= l[i]
        ans %= MOD
else:
    ans = p[0]
    p = p[1:]
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])
    
    l.sort(key=lambda x: abs(x), reverse=True)
    
    for i in range((K-1)//2):
        ans *= l[i]
        ans %= MOD

print(ans)

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

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:
            if ap == []:
                amax.remove(max(am))
                amax.append(max(amin))

            elif max(am)*min(amin) < min(ap)*max(amin):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

print(ans % (10 ** 9 + 7))

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
plus = []
minus=[]
for i in A:
    if i>=0:
        plus.append(i)
    else:
        minus.append(i)
ok = False
if len(plus)>0:
    if n==k:
        ok = (len(minus)%2==0)
    else:
        ok = True
else:
    ok = (k%2==0)
ans = 1
if not ok:
    A.sort(key=abs)
    for i in range(k):
        ans *= A[i]
        ans %= mod
else:
    plus.sort()
    minus.sort(reverse=True)
    if k%2 == 1:
        ans *= plus.pop()
    P = []
    while len(plus) >= 2:
        P.append((plus.pop())*(plus.pop()))
    while len(minus) >= 2:
        P.append((minus.pop())*(minus.pop()))
    P.sort(reverse=True)
    for i in range(k//2):
        ans *= P[i]
        ans %= mod
print(ans)

Solution (Python):
from collections import deque

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) > 0 and len(A_n) > 0 and A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  elif len(A_n) > 0:
    ans_n.append(A_n.popleft())
  elif len(A_p) > 0:
    ans_p.append(A_p.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) > 0 and len(ans_n) > 0 and len(A_p) > 0 and len(A_n) > 0 and ans_p[-1] * A_p[0] >= ans_n[-1] * A_n[0]:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_n) > 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (-a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A_abs = [abs(a) for a in A]
  A_abs.sort()
  for i in range(K):
    ans = (ans * A_abs[i]) % MOD
  ans = (-ans) % MOD
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []

for i in range(N):
    if A[i]>=0:
        p.append(A[i])
    else:
        n.append(A[i])

ok = False

if len(p)>0:
    if N==K:
        if len(n)%2==0:
            ok = True
    else:
        ok = True
else:
    if K%2==0:
        ok = True

if not ok:
    A.sort(key=lambda x: abs(x))
    ans = 1
    
    for Ai in A[:K]:
        ans *= Ai
        ans %= MOD

    print(ans)
    exit()

p.sort(reverse=True)
n.sort()

if K%2==1:
    ans = p[0]
    p = p[1:]
else:
    ans = 1
    
l = []
    
for i in range(len(p)//2):
    l.append(p[2*i]*p[2*i+1])
    
for i in range(len(n)//2):
    l.append(n[2*i]*n[2*i+1])

l.sort(key=lambda x: abs(x), reverse=True)

for li in l[:K//2]:
    ans *= li
    ans %= MOD
    
print(ans)

Solution (Python):
from collections import deque

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) > 0 and len(ans_n) > 0 and len(A_p) > 0 and len(A_n) > 0 and ans_p[-1] * A_p[0] >= ans_n[-1] * A_n[0]:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_n) > 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (-a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A_abs = [abs(a) for a in A]
  A_abs.sort()
  for i in range(K):
    ans = (ans * A_abs[i]) % MOD
  ans = (-ans) % MOD
print(ans)

Solution (Python):
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()
i = 0
j = n - 1
if k % 2 == 1:
    ans *= A[j]
    ans %= p
    j -= 1
    k -= 1
for _ in range(k // 2):
    left = A[i] * A[i + 1]
    right = A[j] * A[j - 1]
    if (left > right):
        ans *= left
        ans %= p
        i += 2
    else:
        ans *= right
        ans %= p
        j -= 2
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x>=0, A)]
neg = [*filter(lambda x: x<0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] < -neg[j]:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1

if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag2 = True
    if i == 0:
        flag2 = True
    elif j == 0:
        flag2 = False
    elif i == len(pos):
        flag2 = False
    elif j == len(neg):
        flag2 = True
    elif pos[i-1]*pos[i] < neg[j-1]*neg[j]:
        flag2 = False

    if flag2:
        ans = (ans * pow(neg[j-1],m-2,m) % m) * pos[i] % m
    else:
        ans = (ans * pow(pos[i-1],m-2,m) % m) * neg[j] % m
    print(ans)

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


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = modint(1)
    if N == K:
        for a in A:
            ans *= a
        return print(ans)
    elif all(a < 0 for a in A) and K % 2 == 1:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
        return print(ans)
    
    A.sort(reverse=True, key=abs)
    if sum(a < 0 for a in A[:K]) % 2 == 0:
        for a in A[:K]:
            ans *= a
    else:
        ans1 = modint(1)  
        ans2 = modint(1)  
        p_remove = False
        x1 = INF
        for a in A[:K][::-1]:
            if a > 0 and not p_remove:
                p_remove = True
                x1 = a
                continue
            ans1 *= a
        n_remove = False
        x2 = INF
        for a in A[:K][::-1]:
            if a < 0 and not n_remove:
                n_remove = True
                x2 = a
                continue
            ans2 *= a
        y1 = 0  
        y2 = 0  
        for a in A[K:]:
            if y1 == 0 and a < 0:
                y1 = a
            if y2 == 0 and a > 0:
                y2 = a
            if y1 != 0 and y2 != 0:
                break
        ans1 *= y1
        ans2 *= y2
        if x1 != INF and x2 != INF:
            if abs(x2*y1) <= abs(x1*y2):
                ans = ans2
            else:
                ans = ans1
        elif x1 == INF and x2 == INF:
            
            ans = 0
        elif x1 == INF:
            
            ans = ans2
        else:
            
            
            
            ans = ans1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) == 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_n) == 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and len(A_p) > 0 and len(A_n) > 0 and ans_p[-1] * A_p[0] >= ans_n[-1] * A_n[0]:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_n) > 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (-a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A_abs = [abs(a) for a in A]
  A_abs.sort()
  for i in range(K):
    ans = (ans * A_abs[i]) % MOD
  ans = (-ans) % MOD
print(ans)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

N,K = map(int,S().split())
A = LI()
mod = 10**9+7

ans = 1

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

B = []  
C = []  
for i in range(N):
    if A[i] >= 0:
        B.append(A[i])
    else:
        C.append(A[i])
b = len(B)  
c = len(C)  

if c == N and K % 2 == 1:
    A.sort(reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)
    exit()



B.sort(reverse=True)
C.sort()
d = 0  
e = 0  



while d + e < K:
    if d + e == K-1:
        ans *= B[d]
        ans %= mod
        d += 1
    else:
        if e >= c-1:
            ans *= B[d]
            ans %= mod
            d += 1
        elif d >= b-1:
            ans *= C[e]*C[e+1]
            ans %= mod
            e += 2
        else:
            if B[d]*B[d+1] < C[e]*C[e+1]:
                ans *= C[e]*C[e+1]
                ans %= mod
                e += 2
            else:
                ans *= B[d]
                ans %= mod
                d += 1

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
A = LIST()

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

a = []
for x in A:
	flg = 0
	if x < 0:
		flg = 1
	a.append([x, abs(x), flg])

a.sort(key = lambda x: -x[1])



flg_sum = sum([x[2] for x in a[:K]])

if flg_sum%2 == 0:
	ans = 1
	for x in a[:K]:
		ans = ans*x[1]%mod
	print(ans)
	exit()


flg = a[K-1][2]
s0 = 0
s1 = 0
for i in range(K, N):
	if a[i][2] != flg:
		s0 = a[K-1][1]
		s1 = a[i][1]
		break

flg = a[K][2]
t0 = 0
t1 = 0
for i in range(K-1, -1, -1):
	if a[i][2] != flg:
		t0 = a[i][1]
		t1 = a[K][1]
		break

if s0+t0 != 0:
	ans = 1
	if s0 == 0:
		for i in range(K):
			if a[i][1] != t0:
				ans = ans*a[i][1]%mod
		print(ans*t1%mod)
		exit()
	elif t0 == 0:
		for i in range(K-1):
			ans = ans*a[i][1]%mod
		print(ans*s1%mod)
		exit()
	elif s1*t0 >= s0*t1 or t0 == 0:
		for i in range(K-1):
			ans = ans*a[i][1]%mod
		print(ans*s1%mod)
		exit()
	else:
		for i in range(K):
			if a[i][1] != t0:
				ans = ans*a[i][1]%mod
		print(ans*t1%mod)
		exit()


ans = 1
for x in a[::-1][:K]:
	ans = ans*x[0]%mod

print(ans)