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(' '))
l = map(int, input().split(' '))

s = 1
if n == k:
	for i in l:
		s *= i
		s %= 1000000007
	print(s)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
			s %= 1000000007
		print(s)

	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k//2):
			if len(pos) >= 2:
				answer.append(pos.pop()*pos.pop())
			else:
				break
		for i in range(k//2):
			if len(neg) >= 2:
				answer.append(neg.pop()*neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
			s %= 1000000007
		print(s)

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

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

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) 
minus.sort() 
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k>=len(plus)-1:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k>=len(minus)-1:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k]*plus[plus_k+1]>minus[minus_k]*minus[minus_k+1]:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)

Solution (Python):
mod = 1000000007
N, K = map(int, input().split())

pos = []
neg = []
A = list(map(int, input().split()))
for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    else:
        neg.append(A[i])

ans = 1
if len(pos) == 0:
    if K % 2 == 0:
        neg.sort(reverse=True)
    else:
        neg.sort()
    for i in range(K):
        ans = (ans * neg.pop()) % mod
elif N == K:
    for i in pos:
        ans = (ans * i) % mod
    for i in neg:
        ans = (ans * i) % mod
else:
    pos.sort()
    neg.sort(reverse=True)
    if K % 2 == 1:
        ans = pos.pop()
    for i in range(K//2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
                for _ in range(2):
                    ans = ans * pos.pop() % mod
            else:
                for _ in range(2):
                    ans = ans * neg.pop() % mod
        elif len(pos) > 1:
            for _ in range(2):
                ans = ans * pos.pop() % mod
        else:
            for _ in range(2):
                ans = ans * neg.pop() % mod


print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p,z=[],[],0
for a in A:
    if a<0:
        m.append(a)
    elif a>0:
        p.append(a)
    else:
        z+=1
m.sort()
p.sort()
mod=10**9+7
from functools import reduce
if (len(p) or K%2==0) and K<len(m)+len(p) or K==len(m)+len(p) and len(m)%2==0:
    r=1
    i,j=0,0
    while i+j<K:
        if i<len(m)-1 and i+j<K-1 and (j>=len(p)-1 or m[i]*m[i+1]>p[-j-1]*p[-j-2]):
            r=r*m[i]*m[i+1]%mod
            i+=2
        else:
            r=r*p[-j-1]%mod
            j+=1
    print(r)
elif z:
    print(0)
else:
    print(reduce(lambda x,y:x*y%mod,(m+p)[-K:]))

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):
import sys

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])

P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod

print(ans)

Solution (Python):

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

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


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


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

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


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


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


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


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

ans_cand=[]

if p!=len(ap):
    ans_cand.append(multarray(ans)*ap[p]%mod)

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

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

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

if N - A.count(0) < K:
    print(0)
    exit(0)

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

if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

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

i = 0
j = 0

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Solution (Python):
def prod(list):
    prod = 1
    for k in list:
        prod = (prod * k) % (10**9+7)
    return prod
    
    


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

plus = []
minus = []

for k in a:
    if k >= 0:
        plus.append(k)
    if k <= 0:
        minus.append(k)

if len(plus) == 0:
    if kk % 2 == 0:
        mi = sorted(minus)
        ans = prod(mi[:kk])
    else:
        mi = sorted(minus, reverse=True)
        ans = prod(mi[:kk])

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

elif n == kk:
    ans = prod(a)
    print(int(ans) % (10**9+7))

else:
    mi = sorted(minus)
    pl = sorted(plus, reverse=True)
    mi.append(0)
    mi.append(0)
    pl.append(0)
    pl.append(0)
    miind = 0
    plind = 0
    ans = 1
    while kk > miind + plind:
        if mi[miind]*mi[miind+1] > pl[plind]*pl[plind+1] and kk != miind + plind + 1:
            ans = (ans*mi[miind]*mi[miind+1]) % (10**9+7)
            miind += 2
        else:
            ans = (ans*pl[plind]) % (10**9+7)
            plind += 1

    print(ans)

Solution (Python):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort(reverse=True)
n=len(arr)
l=0
r=n-1
ans=1
if k%2==1:
    ans=arr[0]
    l=1
m=10**9+7
if ans<0:
    ans=1
    for i in range(k):
        ans*=arr[i]
        ans%=m
    print(ans)
    quit()
for i in range(k//2):
    po=arr[l]*arr[l+1]
    ne=arr[r]*arr[r-1]
    if po>=ne:
        l+=2
        ans*=po
        ans%=m
    else:
        r-=2
        ans*=ne
        ans%=m
print(ans)

Solution (Python):
N,K = map(int,input().split())
MOD = 10**9+7
a = list(map(int,input().split()))
b = []
c = []
d = []
num_z = 0
for val in a:
    if val>0:
        b.append(val)
        d.append(val)
    elif val<0:
        c.append(-val)
        d.append(-val)
    else:
        num_z += 1
        d.append(0)
num_b = len(b)
num_c = len(c)
res = 1
if (N==num_c and K%2==1):
    d = sorted(d)
    for val in d[:K]:
        res = res*val%MOD
    res = -res%MOD
elif (N==K and num_c>0):
    c = sorted(c)
    for val in a:
        res = res*val%MOD
elif num_b==0:
    if K%2==0:
        if num_c >= K:
            c = sorted(c,reverse=True)
            for val in c[:K]:
                res = res*val%MOD
        else:
            res = 0
    else:
        res = 0
else:
    b = sorted(b,reverse=True)
    c = sorted(c,reverse=True)
    bidx = 0
    cidx = 0
    tmp = 0
    if num_b+num_c < K:
        res = 0
    else:
        if num_b >= K:
            bidx = K
        elif num_c>=2:
            bidx = num_b
            cidx = K-bidx
            if (K-num_b)%2==1:
                if cidx == num_c:
                    print(0)
                    exit()
                bidx -= 1
                cidx += 1
        else:
            print(0)
            exit()
        
        for val in b[:bidx]:
            res = res*val%MOD
        for val in c[:cidx]:
            res = res*val%MOD
        for k in range(100000):
            if bidx<=1 or cidx+1 >= num_c:
                break
            if b[bidx-1]*b[bidx-2] > c[cidx]*c[cidx+1]:
                break
            else:
                res *= c[cidx]
                res *= c[cidx+1]
                res = res%MOD
                res = res*pow(b[bidx-1],MOD-2,MOD)
                res = res*pow(b[bidx-2],MOD-2,MOD)
                res = res%MOD
                bidx -= 2
                cidx += 2
print(res%MOD)

Solution (Python):
from functools import reduce

mod = 10 ** 9 + 7

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

A.sort(reverse=True)

ans = 1
l, r = 0, N - 1
if K % 2 == 1:
    ans = A[0]
    l = 1

if ans < 0:
    print(reduce(lambda a, b: a * b % mod, A[:K], 1))
    quit()


for i in range(K // 2):
    L = A[l] * A[l + 1]
    R = A[r] * A[r - 1]
    if L >= R:
        ans *= L
        l += 2
    else:
        ans *= R
        r -= 2
    ans %= mod

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)



from collections import deque

import itertools
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()
    A = deque(A)
    
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    
    
    AA = []
    if N == K:
        ans = 1
        for l in range(N):
            ans *= A[l] 
            ans %=mod
        print(ans % mod)

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)
        ans = 1
        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
            ans %= mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
            ans %= mod
        print(ans % mod)

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) 
            ans %= mod
        print(ans % mod)


if __name__ == "__main__":
    main()

Solution (Python):
import sys




from collections import deque


import bisect






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

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



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()

Solution (Python):
mod = 1000000007
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1

if A[-1] < 0 and K%2 == 1:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    
    if K%2 == 1:
        ans = ans * (A[p]%mod) % mod
        p -= 1
    
    for _ in range(K//2):
        if A[n]*A[n+1] > A[p]*A[p-1]:
            ans = ans * (A[n]%mod) % mod
            ans = ans * (A[n+1]%mod) % mod
            n += 2
        else:
            ans = ans * (A[p]%mod) % mod
            ans = ans * (A[p-1]%mod) % mod
            p -= 2        

print(ans)

Solution (Python):
import sys




from collections import deque


import bisect






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

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



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()

Solution (Python):
mod = 1000000007
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1

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

elif A[-1] < 0 and K%2 == 1:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    
    if K%2 == 1:
        ans = ans * (A[p]%mod) % mod
        p -= 1
    
    for _ in range(K//2):
        if A[n]*A[n+1] > A[p]*A[p-1]:
            ans = ans * (A[n]%mod) % mod
            ans = ans * (A[n+1]%mod) % mod
            n += 2
        else:
            ans = ans * (A[p]%mod) % mod
            ans = ans * (A[p-1]%mod) % mod
            p -= 2        

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import mul
from bisect import bisect_left


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def sign(x):
    if x == 0:
        return 0
    return 1 if x > 0 else -1


def solve(N, K, A, p=10**9+7):
    A.sort(key=lambda a: -abs(a))
    s = 1  
    v = 1  
    idx_minus = -1
    idx_not_minus = -1
    for i in range(K):
        _s = sign(A[i])
        s *= _s
        v *= A[i]
        v %= p
        if _s >= 0:
            idx_not_minus = i
        else:
            idx_minus = i
    if s >= 0 or N == K:
        return v
    
    
    
    a1 = A[idx_minus]
    b1 = max(A[K:])
    
    a2 = A[idx_not_minus]
    b2 = min(A[K:])

    use_1, use_2 = True, True
    if not(idx_minus >= 0 and b1 >= 0):
        use_1 = False
    if not(idx_not_minus >= 0 and b2 < 0):
        use_2 = False
    
    if use_1 and use_2:
        if b1 * a2 >= b2 * a1:
            use_1 = True
            use_2 = False
        else:
            use_1 = False
            use_2 = True
    if use_1:
        v *= pow(a1, p-2, p)
        v %= p
        v *= b1
        v %= p
    elif use_2:
        v *= pow(a2, p-2, p)
        v %= p
        v *= b2
        v %= p
    else:
        
        A.sort(key=lambda a: abs(a))
        s = 1
        v = 1
        for i in range(K):
            _s = sign(A[i])
            s *= _s
            v *= A[i]
            v %= p
    return v


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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):
MOD = 10 ** 9 + 7

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

S = []
T = []

for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

lenS = len(S)
lenT = len(T)

ok = False
if lenS > 0:
    if N == K:
        ok = lenT % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A.sort(key=lambda x: abs(x))
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    S.sort()
    T.sort(reverse=True)
    if K % 2 == 1:
        ans *= S.pop()
    P = []
    while len(S) >= 2:
        x = S.pop()
        x *= S.pop()
        P.append(x)
    while len(T) >= 2:
        x = T.pop()
        x *= T.pop()
        P.append(x)
    P.sort(reverse=True)
    for i in range(K//2):
        ans *= P[i]
        ans %= MOD

print(ans)

Solution (Python):


import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
A.sort(key = lambda x : abs(x)) 
A_zpos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]


nneg_en = False
if A_zpos:
    if K == N:
        if len(A_neg) % 2 == 0:
            nneg_en = True
    else:
        nneg_en = True
else:
    if K % 2 == 0:
        nneg_en = True


if nneg_en: 
    if K % 2 == 1:
        ans = A_zpos.pop() 
        K -= 1
    else:
        ans = 1

    while K > 0:
        
        next_zpos = -1 if len(A_zpos) < 2 else A_zpos[-1] * A_zpos[-2]
        next_neg = -1 if len(A_neg) < 2 else A_neg[-1] * A_neg[-2]
        if next_zpos >= next_neg:
            ans = ans * A_zpos.pop() * A_zpos.pop() % p
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % p
        K -= 2
else:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % p

print(ans)

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

s = [];  t = [];
for a in A:
    if a < 0:
        t.append(a)
    else:
        s.append(a)

P = 10 ** 9 + 7

S = len(s)
T = len(t)
ok = False
if S > 0:
    if N == K:
        ok = (T % 2 == 0)
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if not ok:
    A.sort(key = lambda x: abs(x))  
    for i in range(K):
        ans = ans * A[i] % P
else:   
    s.sort()    
    t.sort(reverse = True)  
    if K % 2 == 1:
        ans *= s.pop() 

    p = []
    while len(s) >= 2:
        x = s.pop()
        x = x * s.pop()
        p.append(x)

    while len(t) >= 2:
        x = t.pop()
        x = x * t.pop()
        p.append(x)

    p.sort(reverse = True)
    for i in range(K // 2):
        ans = ans * p[i] % P


print(ans % P)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,k = readints()
a = readints()

mod = 10**9+7

ans = 1
if n==k:
    for x in a:
        ans *= x
        ans %= mod
else:
    plus = []
    minus = []
    for x in a:
        if x>=0:
            plus.append(x)
        elif x<0:
            minus.append(x)
    if len(minus)==n and k%2==1:
        minus.sort(reverse=1)
        for i in range(k):
            ans*=minus[i]
            ans %= mod
    else:
        plus.sort(reverse=1)
        minus.sort()
        i = 0
        j = 0
        if k%2==1:
            ans *= plus[0]
            i+=1
            k-=1
        lp = len(plus)
        lm = len(minus)
        while k>0:
            if i+1<lp and j+1<lm:
                if plus[i]*plus[i+1] > minus[j]*minus[j+1]:
                    ans *= plus[i]*plus[i+1]
                    i+=2
                else:
                    ans *= minus[j]*minus[j+1]
                    j+=2
            elif i+1<lp:
                ans *= plus[i]*plus[i+1]
                i+=2
            else:
                ans *= minus[j]*minus[j+1]
                j+=2
            ans %= mod
            k-=2
print(ans)

Solution (Python):
import sys
from math import log

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod


def solve():
    mod = 10**9 + 7
    n, k = nm()
    a = nl()
    a.sort(key=abs, reverse=True)

    if max(a) <= 0 or n == k:
        if k & 1:
            b = a[-k:]
        else:
            b = a[:k]
        d = 1
        for x in b:
            d = d * x % mod
        print(d)
        return

    d = 1
    for x in a[:k]:
        d = d * x % mod
    g = [x < 0 for x in a]

    if sum(g[:k]) % 2 == 0:
        print(d)
        return

    b = list(map(lambda x:-10000 if x == 0 else log(abs(x)), a))
    mpi = mmi = -1
    Mpi = Mmi = -1
    for i in range(k):
        if a[i] <= 0:
            mmi = i
        if a[i] >= 0:
            mpi = i
    for i in range(n-1, k-1, -1):
        if a[i] <= 0:
            Mmi = i
        if a[i] >= 0:
            Mpi = i
    if (mpi == -1 or Mmi == -1) and (mmi == -1 or Mpi == -1):
        if 0 in a: d = 0
    elif (mpi == -1 or Mmi == -1):
        d = d * a[Mpi] * modinv(a[mmi], mod) % mod
    elif (mmi == -1 or Mpi == -1):
        d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    else:
        if a[Mpi] * a[mpi] >= a[Mmi] * a[mmi]:
            d = d * a[Mpi] * modinv(a[mmi], mod) % mod
        else:
            d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    print(d)

    return

solve()

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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

if a is None or b is None:
    ans *= d * pow(c,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*c > b*d:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= d * pow(c,-1,MOD)
ans %= MOD
print(ans)

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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

if len(ng)%2 == 0:
    ans = 1
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

ans = 1
if a is None or b is None:
    ans = d
    for v in ng[:-1]:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
elif c is None or d is None:
    ans = a
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz[:-1]:
        ans *= v
        ans %= MOD
else:
    if a*c > b*d:
        ans = a
        for v in ng:
            ans *= v
            ans %= MOD
        for v in pz[:-1]:
            ans *= v
            ans %= MOD
    else:
        ans = d
        for v in ng[:-1]:
            ans *= v
            ans %= MOD
        for v in pz:
            ans *= v
            ans %= MOD
ans %= MOD
print(ans)