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
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

mod = 10**9+7


if n == k:
    ans = 1
    for i in lst1:
        ans *= i
        ans %= mod
    print(ans)
    exit() 

lst1.sort()
i = 0
minus = []
m = 0
while i < n and lst1[i] < 0:
    minus.append(lst1[i])
    m += 1
    i += 1
zero = 0
while i < n and lst1[i] == 0:
    zero += 1
    i += 1
plus = []
p = 0
while i < n:
    plus.append(lst1[i])
    p += 1
    i += 1


if n-zero < k:
    print(0)
    exit()


if p==0 and not even(k):
    if zero:
        print(0)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= minus[-1-i]
            ans %= mod
        print(ans)
        exit()


if n-zero == k and not even(m):
    print(0)
    exit()





pair = []
if m >= 2:
    for i in range(0,m-1,2): 
        pair.append(minus[i]*minus[i+1])

ans = 1
midx = 0 
pidx = 0 
plus.reverse() 
while k:
    if k == 1:
        if pidx < len(plus):
            ans *= plus[pidx]
            ans %= mod
            k -= 1
            pidx += 1
        else:
            print(0)
            exit()
    elif k == 2:
        if midx < len(pair) and pidx+1 < len(plus):
            if pair[midx] >= plus[pidx]*plus[pidx+1]:
                ans *= pair[midx]
                ans %= mod
                k -= 2
            else:
                ans *= plus[pidx]*plus[pidx+1]
                ans %= mod
                k -= 2

        elif midx < len(pair):
            ans *= pair[midx]
            ans %= mod
            k -= 2
        else:
            ans *= plus[pidx]*plus[pidx+1]
            ans %= mod
            k -= 2
        
        break
    elif k >= 3:
        if midx < len(pair):
            if pidx+2 < len(plus): 
                if pair[midx] >= plus[pidx+1]*plus[pidx+2]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx+1 < len(plus): 
                if pair[midx] >= plus[pidx]*plus[pidx+1]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx < len(plus): 
                if pair[midx] >= plus[pidx]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            else: 
                ans *= pair[midx]
                ans %= mod
                midx += 1
                k -= 2

                
        else:
            ans *= plus[pidx]
            ans %= mod
            pidx += 1
            k -= 1

print(ans)

Solution (Python):
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
am = []
ap = []
for ai in a:
    if ai > 0:
        ap.append(ai)
    elif ai < 0:
        am.append(-ai)
am.sort(reverse=True)
ap.sort(reverse=True)

nm = len(am)
np = len(ap)
nz = n - np - nm



if np + nm < k:
    ans = 0
elif np == 0:
    if k % 2 == 1:
        if nz > 0:
            ans = 0
        else:
            am.sort()
            ans = -1 + MOD
            for i in range(k):
                ans *= am[i]
                ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
        if k - np + 1 > nm:
            if nz > 0:
                ans = 0
            else:
                if nm % 2 == 1:
                    ans = -1 + MOD
                else:
                    ans = 1
                for i in range(np):
                    ans *= ap[i]
                    ans %= MOD
                for i in range(nm):
                    ans *= am[i]
                    ans %= MOD
        else:
            while idx1 >= 2 and idx2 + 1 < nm and \
                ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
                idx1 -= 2
                idx2 += 2
            ans = 1
            for i in range(idx1):
                ans *= ap[i]
                ans %= MOD
            for i in range(idx2):
                ans *= am[i]
                ans %= MOD
    else:
        idx1 = np
        idx2 = k - np
        while idx1 >= 2 and idx2 + 1 < nm and \
            ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
            idx1 -= 2
            idx2 += 2
        ans = 1
        for i in range(idx1):
            ans *= ap[i]
            ans %= MOD
        for i in range(idx2):
            ans *= am[i]
            ans %= MOD
else:
    idx1 = k
    idx2 = 0
    while idx1 >= 2 and idx2 + 1 < nm and \
        ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        ans %= MOD

print(ans)

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

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


















pluslist = []
minuslist = []
zerocnt = 0
for i in range(len(A)):
  if A[i] > 0:
    pluslist.append(A[i])
  elif A[i] < 0:
    minuslist.append(A[i])
  else:
    zerocnt += 1
    

if N - zerocnt < K:
  print(0)
  exit(0)
  
if K % 2 == 1 and len(pluslist) == 0:
  
  if zerocnt > 0:
    print(0)
    exit(0)
  
  minuslist = sorted(minuslist, reverse = True)
  ans = 1
  for i in range(K):
    ans *= minuslist[i]
    ans %= DIV
  print(ans)
  exit(0)
  
if K + zerocnt == N:
  if len(minuslist) % 2 == 1 and zerocnt > 0:
    print(0)
    exit(0)
  else:
    ans = 1
    for p in pluslist:
      ans *= p
      ans %= DIV
    for m in minuslist:
      ans *= m
      ans %= DIV
    print(ans)
    exit(0)


pluslist = sorted(pluslist, reverse = True)
minuslist = sorted(minuslist)
from collections import deque

plusq = deque(pluslist)
minusq = deque(minuslist)

ans = 1


if K % 2 == 1 and len(plusq) > 0:
  ans *= plusq.popleft() 
  K -= 1

for i in range(K // 2):
  p = None
  m = None
  if len(plusq) >= 2:
    p1 = plusq.popleft()
    p2 = plusq.popleft()
    p = p1 * p2
  if len(minusq) >= 2:
    m1 = minusq.popleft()
    m2 = minusq.popleft()
    m = m1 * m2
  if p is None and m is None:
    ans *= (minusq.popleft() * plusq.popleft()) % DIV
    continue
  if m is None:
    ans *= p % DIV
    ans %= DIV
    continue
  if p is None:
    ans *= m % DIV
    ans %= DIV
    continue
  if p > m:
    ans *= p % DIV
    ans %= DIV
    minusq.appendleft(m2)
    minusq.appendleft(m1)
  else:
    ans *= m % DIV
    ans %= DIV
    plusq.appendleft(p2)
    plusq.appendleft(p1)

print(ans)

Solution (Python):
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
MOD = 10**9 + 7
def calc(X):
  ans = 1
  for x in X:
    ans *= x
    ans %= MOD
  return ans

def solve(A):
  if N == K:
    return calc(A)
  if max(A) < 0 and K % 2:
    return calc(sorted(A, reverse=True)[:K])
  
  sA = sorted(((abs(a), -1 if a < 0 else 1) for a in A), reverse=True)
  
  cn = 0
  for i in range(K):
    if sA[i][1] < 0:
      cn += 1
  if cn % 2 == 0:
    return calc([s[0] for s in sA[:K]])
  pA = sorted([abs(a) for a in A if a >= 0], reverse=True)
  nA = sorted([abs(a) for a in A if a < 0], reverse=True)
  
  if (len(nA) >= cn + 1 and len(pA) >= K - cn - 1 and K - cn - 1 >= 0 and
      len(nA) >= cn - 1 and len(pA) >= K - cn + 1):
    candidates = []
    candidates.append((nA[cn-1] * nA[cn], calc(pA[:K-cn-1] + nA[:cn+1])))
    candidates.append((pA[K-cn-1] * pA[K-cn], calc(pA[:K-cn+1] + nA[:cn-1])))
    
    return(max(candidates)[1])
    
  if len(nA) >= cn + 1 and len(pA) >= K - cn - 1 and K - cn - 1 >= 0:
    
    return(calc(pA[:K-cn-1] + nA[:cn+1]))
  if len(nA) >= cn - 1 and len(pA) >= K - cn + 1:
    
    return(calc(pA[:K-cn+1] + nA[:cn-1]))
  

print(solve(A))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def solve():
    N, K = mapint()
    As = list(mapint())
    mod = 10**9+7
    pos = []
    neg = []
    for a in As:
        if a>=0:
            pos.append(a)
        else:
            neg.append(a)

    pos.sort(reverse=True)
    neg.sort()
    lenp = len(pos)
    lenn = len(neg)
    if not pos and K%2==1:
        ans = 1
        for i, n in enumerate(neg[::-1]):
            ans *= n
            ans %= mod
            if i==K-1:
                break
        return ans
    if lenp+lenn==K and (K-lenp)%2==1:
        ans = 1
        pos.extend(neg)
        pos.sort(reverse=True)
        for i, p in enumerate(pos):
            ans *= p
            ans %= mod
            if i==K-1:
                break
        return ans
    ans = 1
    pcnt = 0
    ncnt = 0
    for i in range(K//2):
        if pcnt*2+1>=lenp:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
        elif ncnt*2+1>=lenn:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        elif pos[pcnt*2]*pos[pcnt*2+1]>neg[ncnt*2]*neg[ncnt*2+1]:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        else:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
    if K%2==1:
        ans *= pos[pcnt*2]
        ans %= mod
    return ans

print(solve())

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

pos, neg = [], []
zero_count = 0

for x in a:
	if x > 0:
		pos.append(x)
	elif x < 0:
		neg.append(x)
	else:
		zero_count += 1














MOD = 10**9 + 7

neg = list(sorted(neg))
pos = list(reversed(sorted(pos)))

if len(pos) >= k:
	
	pos_res = pos[:k]
	idx = 0
	while idx + 1 < len(neg) and pos_res[k - idx - 1] * pos_res[k - idx - 2] < neg[idx] * neg[idx + 1]:
		idx += 2

	result = 1
	for i in range(idx):
		result = result * neg[i] % MOD

	for i in range(k - idx):
		result = result * pos[i] % MOD

	print(result)

else:
	
	left = k - len(pos)	
	if left % 2 == 1:
		if len(pos) > 0:
			left += 1
		else:
			left = 1000000000
	if left > len(neg):
		
		b = list(sorted(map(abs, a)))
		result = 1
		for i in range(k):
			result = result * b[i] % MOD
		print(-result % MOD)
	else:
		
		idx = left
		pos_shift = 0
		while idx + 1 < len(neg) and pos_shift + 1 < len(pos) and pos[len(pos) - pos_shift - 1] * pos[len(pos) - pos_shift - 2] < neg[idx] * neg[idx + 1]:
			idx += 2
			pos_shift += 2

		result = 1
		for i in range(idx):
			result = result * neg[i] % MOD

		for i in range(k - idx):
			result = result * pos[i] % MOD

		print(result)

Solution (Python):
def main():

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

    mod = pow(10, 9) + 7

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

    
    if len(pos) + len(neg) < K:
        return 0

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

    cnt_p, cnt_n = 0, 0
    h = []
    for v in pos:
        h.append([v, 1])
    for v in neg:
        h.append([-v, -1])

    h.sort(reverse = True)
    v = 1
    for k in range(K):
        if h[k][1] > 0:
            cnt_p += 1
        else:
            cnt_n += 1

    if cnt_n % 2 == 0: 
        v = 1
        for i in range(cnt_p):
            v *= pos[i]
            v %= mod
        for j in range(cnt_n):
            v *= neg[j]
            v %= mod
        return v
    else: 
        if cnt_p < len(pos) and cnt_n < len(neg) and cnt_p > 0: 
            
            if pos[cnt_p] * pos[cnt_p-1] > abs(neg[cnt_n]) * abs(neg[cnt_n-1]):
                cnt_p += 1
                cnt_n -= 1
            else:
                cnt_p -= 1
                cnt_n += 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_p < len(pos) and cnt_n > 0:
            cnt_p += 1
            cnt_n -= 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_n < len(neg) and cnt_p > 0:
            cnt_p -= 1
            cnt_n += 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        else:
            if zero > 0:
                return 0
            else:
                h.sort()
                v = 1
                for i in range(K):
                    v *= h[i][0] * h[i][1]
                    v %= mod
                return v



if __name__ == '__main__':
    print(main())

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
A1 = []  
A2 = []
for i in range(N):
    if A[i] > 0:
        A1.append(A[i])
    if A[i] < 0:
        A2.append(-A[i])
A1.sort(reverse=True)
A2.sort(reverse=True)
ans = 1
if max(A)< 0:
    if K%2 == 0:
        for i in range(K):
            ans = (ans * A2[i])%mod
    else:
        A2.sort()
        for i in range(K):
            ans = (ans * A2[i])%mod
            ans = (mod - ans)%mod
elif max(A) == 0:
    if K%2 == 1:
        ans = 0
    else:
        if len(A2) >= K:
            for i in range(K):
                ans = (ans * A2[i])%mod
        else:
            ans = 0
else:
    A3 = []
    for i in range(len(A2)//2):
        A3.append(A2[2 * i] * A2[2 * i + 1])
    A4 = []
    A5 = []
    for i in range(len(A1)//2):
        A4.append(A1[2 * i] * A1[2 * i + 1])
    for i in range((len(A1) - 1)//2):
        A5.append(A1[2 * i + 1] * A1[2 * i + 2])
    if len(A1) + 2 * len(A3) < K:
        if N == K:
            for i in range(N):
                ans = (ans * A[i])%mod
        else:
            ans = 0
    else:
        if K%2 == 0:
            A6 = A3 + A4
            A6.sort(reverse=True)
            for i in range(K//2):
                ans = (ans * A6[i])%mod
        else:
            A6 = A3 + A5
            A6.sort(reverse=True)
            ans = A1[0]
            for i in range((K - 1)//2):
                ans = (ans * A6[i])% mod
print(ans)

Solution (Python):

"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
flag0 = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
        elif A[i] == 0:
            flag0 = 1
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lp:
                ans = ans * A[i] % mod
        ans = ans * A[rm] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lm:
                ans = ans * A[i] % mod
        ans = ans * A[rp] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        if flag0:
            print(0)
        else:
            print(ans)

    else:
        if ans1 > 0 and ans2 > 0:
            if A[rm]*A[lm] > A[rp]*A[lp]:
                print(ans1)
            else:
                print(ans2)
        else:
            print(max(ans1,ans2))

Solution (Python):
from collections import deque
MOD = pow(10,9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
P = []; M = []; Z = []
for i in range(N):
  if A[i] >0:
    P.append(A[i])
  elif A[i] <0:
    M.append(A[i])
  else:
    Z.append(0)
P.sort(reverse=True)
M.sort(reverse=True)
ans = 1
if K == 1:
  print(P[0]%MOD)
  exit()
if len(Z) > N-K:
  print(0)
  exit()
if len(M) == 0: 
  for i in range(K):
    ans = ans*P[i]%MOD
  print(ans)
  exit()
if len(P) == 0: 
  if K%2 == 1 and len(Z) > 0:
    print(0)
    exit()
  if K%2 == 1:
    for i in range(K):
      ans = ans*M[i]%MOD
  else:
    M.sort()
    for i in range(K):
      ans = ans*M[i]%MOD
  print(ans)
  exit()

L = [[],[]]
M.sort()
P = deque(P); M = deque(M)
pm = [0,0] 
pnow = 0; mnow = 0


for i in range(K):
  if not P:
    temp = M.popleft()
    pm[1] +=1
    L[1].append(temp)
  elif not M:
    temp = P.popleft()
    pm[0] +=1
    L[0].append(temp)
  elif P and M:
    if P[0] >= abs(M[0]):
      temp = P.popleft()
      pm[0] += 1
      L[0].append(temp)
    else:
      temp = M.popleft()
      pm[1] += 1
      L[1].append(temp)



if pm[1]%2 == 1:
  if not P and not M:
    pass
  elif not M: 
    L[1].pop()
    L[0].append(P[0])
  elif not P: 
    L[0].pop()
    L[1].append(M[0])
  elif M and P:
    if L[0] and L[1]:
      if L[0][-1]*P[0] >= L[1][-1]*M[0]:
        L[1].pop()
        L[0].append(P[0])
      else:
        L[0].pop()
        L[1].append(M[0])
    elif not L[0]:
      L[1].pop()
      L[0].append(P[0])
    elif not L[1]:
      L[0].pop()
      L[1].append(M[0])

for num in range(2):
  for s in L[num]:
    ans = ans*s%MOD
print(ans)

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

def solve(N,K,A):
    prod = lambda x,y : ((x*y) % MOD)
    if N == K:
        return reduce(prod,A,1) % MOD
    A.sort()
    minus = [a for a in A if a < 0][::-1]
    plus = [a for a in A if a > 0][::-1]


    if K % 2 == 1 and len(plus) == 0:
        if 0 in A:
            return 0
        else:
            ans = reduce(prod,minus[:K],1)
            return ans % MOD

    ans = 1
    if K % 2 == 1:
        ans *= plus[0]
        plus2 = [p*q for p,q in zip(plus[1::2],plus[2::2])]
        minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
        cand = sorted((plus2 + minus2),reverse=True)
        if len(cand) < K//2:
            return 0
        ans *= reduce(prod,cand[:K//2],1)
        ans %= MOD
    else:
        plus2 = [p*q for p,q in zip(plus[::2],plus[1::2])]
        minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
        cand = sorted((plus2 + minus2),reverse=True)
        if len(cand) < K//2:
            return 0
        ans *= reduce(prod,cand[:K//2],1)
        ans %= MOD
    return ans

print(solve(N,K,A))

exit()

import random
from itertools import combinations
def ans(N,K,A):
    ans = -10**10
    for itr in combinations(range(N),K):
        t = 1
        for i in itr:
            t *= A[i]
        ans = max(ans,t)
    return ans % MOD

for i in range(100):
    N = 5 
    K = random.randint(1,N)
    A = [random.randint(-10,10) for i in range(N)]
    if solve(N,K,A) != ans(N,K,A):
        print(N,K,A)
        print(solve(N,K,A),ans(N,K,A))
        exit()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
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 [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    from bisect import bisect_left, bisect_right
    N, K = MAP()
    A = LIST()
    A.sort()
    neg = bisect_left(A, 0)
    pos = bisect_right(A, 0)
    negative = A[:neg]
    zeros = A[neg:pos]
    positive = list(reversed(A[pos:]))
    if len(negative) + len(positive) < K:
        
        print(0)
        return
    if len(positive) == 0:
        if K % 2 == 1:
            if len(zeros) > 0:
                
                print(0)
                return
            else:
                
                ans = 1
                for n in negative[-K:]:
                    ans *= (-n)
                    ans %= MOD
                ans *= -1
                print(ans % MOD)
                return
        else:
            
            ans = 1
            for n in negative[:K]:
                ans *= (-n)
                ans %= MOD
            print(ans % MOD)
            return

    if len(negative) + len(positive) == K:
        if len(negative) % 2 == 1:
            if len(zeros) > 0:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    ans *= a
                    ans %= MOD
                print(ans % MOD)
                return
    
    
    
    
    new_neg = []
    for i in range(0, len(negative)-1, 2):
        new_neg.append(negative[i]*negative[i+1])

    phead = 0
    nhead = 0

    k = K
    ans = 1
    while k > 1 and phead+2 < len(positive) and nhead < len(new_neg):
        if k >= 3:
            
            if new_neg[nhead] < positive[phead+1]*positive[phead+2]:
                ans *= positive[phead]
                ans %= MOD
                phead += 1
                k -= 1
                continue
            else:
                ans *= new_neg[nhead]
                ans %= MOD
                nhead += 1
                k -= 2
                continue
        if k == 2:
            if new_neg[nhead] < positive[phead+1]*positive[phead]:
                ans *= positive[phead+1]*positive[phead]
                ans %= MOD
                print(ans)
                return
            else:
                ans *= new_neg[nhead]
                ans %= MOD
                print(ans)
                return
    if nhead >= len(new_neg):
        
        
        while k > 0:
            ans *= positive[phead]
            ans %= MOD
            phead += 1
            k -= 1
        print(ans)
        return
    if phead + 2 >= len(positive):
        
        if k % 2 == 0:
            
            pcand = -INF
            if phead + 1 < len(positive):
                pcand = positive[phead]*positive[phead+1]

            while k > 1 and nhead < len(new_neg):
                ncand = new_neg[nhead]
                if ncand < pcand:
                    ans *= pcand
                    ans %= MOD
                    pcand = -INF
                    k -= 2
                else:
                    ans *= ncand
                    ans %= MOD
                    nhead += 1
                    k -= 2
            if k != 0:
                ans *= pcand
                ans %= MOD

            print(ans % MOD)
            return
        else:
            
            
            
            ans *= positive[phead]
            ans %= MOD
            while k > 1:
                ncand = new_neg[nhead]
                ans *= ncand
                ans %= MOD
                k -= 2
                nhead += 1
            print(ans)
            return
    if k == 1:
        ans *= positive[phead]
        ans %= MOD
        print(ans)
        return
    
    
    
    
    
    
    
    
    return


if __name__ == '__main__':
    main()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
from fractions import Fraction

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


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    
    
    

    
    

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives+zeros and k%2==1):
        
        
        A.sort(key=lambda a: abs(a))
        
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        
        
        A.sort(reverse=True, key=lambda a: abs(a))
        
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                

        
        
        
        if n_count%2 == 1:
            first_p = None
            first_n = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    first_p = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    a = A[i]
                    if a < 0:
                        ans_b = ans*inv(last_p, MOD) * a
                        first_n = a
                        break
                if first_n is not None:
                    if first_p is not None:
                        xx = Fraction(abs(first_p), abs(last_n))
                        yy = Fraction(abs(first_n), abs(last_p))
                        
                        
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            if first_n is None and first_p is None:
                ans_a = 0
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Solution (Python):

Q = int(1e9 + 7)

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

A = sorted(A)

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= Q
    print(ans)
    exit()
elif K == 1:
    ans = A[-1] % Q
    print(ans)
    exit()

A_mi, A_0, A_pl = [], [], []
for a in A:
    if a > 0:
        A_pl.append(a)
    elif a < 0:
        A_mi.append(a)
    else:
        A_0.append(a)


if len(A_mi) + len(A_pl) < K:
    print(0)
    exit()


if N == len(A_pl):
    ans, c = 1, 0
    for a in reversed(A_pl):
        ans *= a
        ans %= Q
        c += 1
        if c == K:
            break
    print(ans)
    exit()


if N == len(A_mi) + len(A_0):
    if K % 2 == 0:
        ans, c = 1, 0
        for a in A_mi:
            ans *= a
            ans %= Q
            c += 1
            if c == K:
                break
        print(ans)
        exit()
    else:
        if len(A_0) > 0:
            print(0)
            exit()
        else:
            ans, c = 1, 0
            for a in reversed(A_mi):
                ans *= a
                ans %= Q
                c += 1
                if c == K:
                    break
            print(ans)
            exit()


cost_2 = []
if len(A_mi) > 1:
    for i in range(0, len(A_mi)-1, 2):
        cost_2.append(A_mi[i] * A_mi[i + 1])

c = 0
ans = 1

if K % 2 == 0:
    while True:
        if len(cost_2) > 0:
            c2 = cost_2[0]
        else:
            c2 = 0
        if len(A_pl) > 1:
            pl2 = A_pl[-1] * A_pl[-2]
        else:
            pl2 = 0
        if c2 > pl2:
            ans *= c2
            cost_2.pop(0)
        else:
            ans *= pl2
            A_pl.pop(-1)
            A_pl.pop(-1)
        ans %= Q
        c += 2
        if c == K:
            break
    print(ans)
else:
    while True:
        if (K - c > 1) and (len(cost_2) > 0):
            c2 = cost_2[0]
            if len(A_pl) > 2:
                pl2 = A_pl[-1] * A_pl[-2]
            else:
                pl2 = 0
            if c2 >= pl2:
                ans *= c2
                cost_2.pop(0)
            else:
                ans *= pl2
                A_pl.pop(-1)
                A_pl.pop(-1)
            ans %= Q
            c += 2
        else:
            ans *= A_pl[-1]
            ans %= Q
            c += 1
            A_pl.pop(-1)
        if K == c:
            break

    print(ans)

Solution (Python):
import sys

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1

if K%2==1:  
    score*=A[0]
    A.pop(0)
    K-=1



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

M=M[::-1]
t=0
p,m=0,0
while t<=K:
    if score<0:  
        P=P[::-1]
        M=M[::-1]
        if 0 in M:
            print(0)
            sys.exit()
    if t+2<=K:
        if 2*p+1<len(P) and 2*m+1<len(M):
            if P[2*p]*P[2*p+1] >= M[2*m]*M[2*m+1]:
                score*=P[2*p]*P[2*p+1]
                p+=1
                t+=2
            else:
                score*=M[2*m]*M[2*m+1]
                m+=1
                t+=2
        elif 2*p+1<len(P):
            score*=P[2*p]*P[2*p+1]
            p+=1
            t+=2
        elif 2*m+1<len(M):
            score*=M[2*m]*M[2*m+1]
            m+=1
            t+=2
        else:  
            score*=P[-1]*M[-1]
            break
    elif t+1<=K:
        if 2*p<len(P):
            score*=P[2*p]
        else:
            score*=M[2*m]
        break
    else:
        break
    score%=mod

print(score%mod)