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

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


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


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    n, k = map(int, input().split())
    a = sorted([(abs(i), (1 if i > 0 else -1)) for i in map(int, input().split())], reverse=True)
    if n == k:
        s = 1
        for x in a:
            s = s * x[0] * x[1] % mod
        print(s)
        return
    if len([i for i in a if i[1] == -1]) == n:
        if k % 2 == 0:
            s = 1
            for i in a[:k]:
                s = (s * i[0]) % mod
            print(s)
        else:
            s = 1
            for i in a[-k:]:
                s = (s * i[0]) % mod
            print((-s) % mod)
        return
    s = 1
    c = 1
    for i in range(k):
        s = s * a[i][0] % mod
        c *= a[i][1]
    if c == 1:
        print(s)
        return

    x_minus1 = -1
    x_plus1 = -1
    for i in range(k):
        if a[i][1] == -1:
            x_minus1 = a[i][0]
    for i in range(k, n):
        if a[i][1] == 1:
            x_plus1 = a[i][0]
            break

    x_minus2 = -1
    x_plus2 = -1
    for i in range(k):
        if a[i][1] == 1:
            x_minus2 = a[i][0]
    for i in range(k, n):
        if a[i][1] == -1:
            x_plus2 = a[i][0]
            break
    if x_minus1 == -1 or x_plus1 == -1:
        s = (s * inverse(x_minus2)) % mod * x_plus2 % mod
        print(s)
        return
    if x_minus2 == -1 or x_plus2 == -1:
        s = (s * inverse(x_minus1)) % mod * x_plus1 % mod
        print(s)
        return
    if x_plus1 * x_minus2 > x_plus2 * x_minus1:
        s = (s * inverse(x_minus1)) % mod * x_plus1 % mod
    else:
        s = (s * inverse(x_minus2)) % mod * x_plus2 % mod
    print(s)
main()

Solution (Python):
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
sign = dict({-1:0,0:0,1:0})
for a in A:
    if a<0:
        sign[-1]+=1
    elif a>0:
        sign[1]+=1
    else:
        sign[0]+=1
if sign[1]==0 and K%2!=0:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif sign[1]==0 and K%2==0:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort()
    ans = 1
    i,j = 0,N-1
    while K>0:
        if K>1 and A[i]*A[i+1]>=A[j]*A[j-1]:
            ans *= A[i]*A[i+1]
            ans %= MOD
            i += 2
            K -= 2
        else:
            ans *= A[j]
            ans %= MOD
            j -= 1
            K -= 1
print(ans)

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

A.sort()

mod = int(1e9+7)
AM = []
AP = []
AZC = 0
for a in A:
  if a < 0:
    AM.append(a)
  elif a == 0:
    AZC += 1
  else:
    AP.append(a)





if N-K < AZC:
  print(0)
  exit(0)

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



if len(AP) == 0 and K%2 == 1:
  if AZC > 0:
    print(0)
  else:
    wk = 1
    for i in range(K):
      wk *= AM[-1-i]
      wk %= mod
    print(wk)
  exit(0)  
   



wk = 1
if K%2 == 1:
  wk *= AP.pop(-1)
  wk %= mod
  
K = K // 2
mi, pi = 0, 0
AP = AP[::-1]
while K>0:
  mwk = AM[mi] * AM[mi + 1] if mi + 1 < len(AM) else 0
  pwk = AP[pi] * AP[pi + 1] if pi + 1 < len(AP) else 0
  if mwk <= pwk:
    wk *= pwk % mod
    pi += 2
  else:
    wk *= mwk % mod
    mi += 2
  
  wk %= mod
  K -= 1
print(wk)

Solution (Python):
from bisect import bisect_left

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

pos = A[bisect_left(A, 0):]
pos.reverse()
neg = A[:bisect_left(A, 0)]

mod = 10**9+7
ans = 1
if len(pos) == 0 and K % 2 == 1:
    for i in range(K):
        ans *= neg[-i-1]
        ans %= mod
elif N == K:
    for i in range(K):
        ans *= A[i]
        ans %= mod
else:
    p, n = 0, 0
    for i in range(0, K-1, 2):
        v1 = 0
        v2 = 0
        if K % 2 == 0:
            if len(pos) >= p + 2:
                v1 = pos[p] * pos[p+1]
        else:
            if len(pos) >= p + 3:
                v1 = pos[p] * pos[p+1]

        if len(neg) >= n + 2:
            v2 = neg[n] * neg[n+1]

        if v2 > v1:
            ans *= v2
            ans %= mod
            n += 2
        else:
            ans *= v1
            ans %= mod
            p += 2

    if K % 2 == 1:
        ans *= pos[p]
        ans %= mod

print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

pos = []
neg = []

zero = 0

for i in a:
    
    
    if i==0: zero += 1
    elif i > 0: pos.append(i)
    else: neg.append(-i)


MOD = 10**9+7

if n - zero < k: 
    print(0)
elif pos == []: 
    if k%2==0:
        neg.sort(reverse=True)
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans)
    else:
        if zero:
            print(0)
        else: 
            neg.sort()
            ans = -1
            for i in range(k):
                ans *= neg[i]
                ans %= MOD
            print(ans%MOD)
            
else: 
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    cp = len(pos)
    cn = len(neg)
    
    i = j = 0    
    for _ in range(k):
        if i == cp:
            j += 1
        elif j == cn:
            i += 1
        else:
            if pos[i] > neg[j]:
                i += 1
            else:
                j += 1
    
    
    if j%2 == 0:
        ans = 1
        for x in pos[:i]:
            ans *= x
            ans %= MOD
        for x in neg[:j]:
            ans *= x
            ans %= MOD
        print(ans)
            
    else:
        can_i = i and j < cn
        can_j = j and i < cp
        if not can_i and not can_j:
            if zero: print(0)
            else:
                ans = -1
                for x in pos[:i]:
                    ans *= x
                    ans %= MOD
                for x in neg[:j]:
                    ans *= x
                    ans %= MOD
                print(ans)
            exit()
                
                
        if not can_i:
            j -= 1
            i += 1
        elif not can_j:
            j += 1
            i -= 1
        else:
            if pos[i]*pos[i-1] >= neg[j]*neg[j-1]:
                j -= 1
                i += 1
            else:
                j += 1
                i -= 1

        ans = 1                
        for x in pos[:i]:
            ans *= x
            ans %= MOD
        for x in neg[:j]:
            ans *= x
            ans %= MOD
        print(ans)

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

B = []
for a in A:
    B.append([abs(a), a])

B.sort(reverse=True)
ans =  1
pre_nega = 0
pre_posi = 0
num_posi = num_nega = 0
for count, (b, a) in enumerate(B, 1):
    ans *= b
    ans %= MOD
    if a < 0:
        pre_nega = a
        num_nega += 1
    if a > 0:
        pre_posi = a
        num_posi += 1
    if count == K:
        break

if num_nega % 2 == 0:
    print(ans)
    quit()

flag_nega = True
flag_posi = True
next_nega = next_posi = 0
for b, a in B[K:]:
    if flag_nega and a < 0:
        next_nega = a
        flag_nega = False
    elif flag_posi and a > 0:
        next_posi = a
        flag_posi = False

if next_nega != 0 and num_posi > 0:
    if next_posi != 0 and num_nega > 0:
        if next_nega * pre_nega > next_posi * pre_posi:
            ans *= abs(next_nega)
            ans *= pow(pre_posi, MOD-2, MOD)
            ans %= MOD
        else:
            ans *= next_posi
            ans *= pow(abs(pre_nega), MOD-2, MOD)
            ans %= MOD
    else:
        ans *= abs(next_nega)
        ans *= pow(pre_posi, MOD-2, MOD)
        ans %= MOD
else:
    if next_posi != 0 and num_nega > 0:
        ans *= next_posi
        ans *= pow(abs(pre_nega), MOD-2, MOD)
        ans %= MOD
    else:
        if 0 in A:
            ans = 0
        else:
            ans = 1
            B.sort()
            for count, (b, a) in enumerate(B, 1):
                ans *= a
                ans %= MOD
                if count == K:
                    break

print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    Lp=[]
    Lm=[]
    Lz=[]
    for i in range(N):
        if A[i]==0:
            Lz.append(0)
        elif A[i]>0:
            Lp.append(A[i])
        else:
            Lm.append(A[i])
            
    Lp.sort(reverse=True)
    Lm.sort()
    
    Np=len(Lp)
    Nm=len(Lm)
    
    if len(Lp)+len(Lm)<K:
        print(0)
        exit()
    if K==1:
        print(max(A))
        exit()
    if max(A)<=0:
        if K%2==0:
            A.sort()
        else:
            A.sort(reverse=True)
        ans=1
        for i in range(K):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    if K==N:
        ans=1
        for i in range(N):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    
    Lp.append(0)
    Lp.append(0)
    Lp.append(0)
    Lm.append(0)
    Lm.append(0)
    nowp=0
    nowm=0
    
    ans=1
    if K%2==0:
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    else:
        ans=Lp[0]
        nowp+=1
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    print(ans)
        
            

        
 
    
            
            

main()

Solution (Python):


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


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    if N==1:
        print(A[0])
        exit()
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if i+1>=N:
            break
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if i+1<N and len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
                ans=(ans*A2n[ni])%MOD
                K-=2
                ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()

Solution (Python):
N,K=map(int,input().split())
L=list(map(int,input().split()))
P=[]
M=[]
Z=[]
mod=10**9+7
for i in L:
    if i>0:
        P.append(i)
    elif i<0:
        M.append(i)
    else:
        Z.append(i)

P.sort(reverse=True)
M.sort()

if len(P)==0:
    if K%2==0:
        M+=Z
        ans=1
        
        for i in range(K):
            ans*=M[i]
            ans%=mod
        print(ans)
    else:
        if len(Z)>0:
            print(0)
        else:
            M.sort(reverse=True)
            ans=1
            for i in range(K):
                ans*=M[i]
                ans%=mod
            print(ans)
else:
    if N==K:
        ans=1
        for i in range(N):
            ans*=L[i]
            ans%=mod
        print(ans)
    elif K%2==0:
        P+=[0,0]
        P+=Z
        M+=[0,0]
        M+=Z
        ans=1
        p=0
        m=0
        for i in range(K//2):
            if P[p*2]*P[p*2+1]>M[m*2]*M[m*2+1]:
                ans*=(P[p*2]*P[p*2+1])
                ans%=mod
                p+=1
            else:
                ans*=(M[m*2]*M[m*2+1])
                ans%=mod
                m+=1
        print(ans)
    else:
        P+=[0,0]
        P+=Z
        M+=[0,0]
        M+=Z
        ans=P[0]
        p=1
        m=0
        for i in range(K//2):
            if P[p*2]*P[p*2-1]>M[m*2]*M[m*2+1]:
                ans*=(P[p*2]*P[p*2-1])
                ans%=mod
                p+=1
            else:
                ans*=(M[m*2]*M[m*2+1])
                ans%=mod
                m+=1
        print(ans)

Solution (Python):
from math import log10
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
a.sort()

cnt_neg = 0
cnt_pos = 0
for i in a:
   if i <= 0:
      cnt_neg += 1
   else:
      cnt_pos += 1
is_minus = False
k_tmp = k
while k_tmp > 0:
   if k_tmp >= 2:
      if cnt_neg >= 2:
         cnt_neg -= 2
      elif cnt_pos >= 2:
         cnt_pos -= 2
      else:
         is_minus = True
         break
      k_tmp -= 2
   else:
      if cnt_pos > 0:
         cnt_pos -= 1
         k_tmp -= 1
      else:
         is_minus = True
         break

k_1 = k
ans1 = 1
l = 0
r = n - 1
if k_1 % 2:
   ans1 *= a[-1]
   r -= 1
   k_1 -= 1
while k_1 >= 2:
   if a[l] * a[l+1] > a[r-1] * a[r]:
      ans1 *= a[l] * a[l+1]
      l += 2
   else:
      ans1 *= a[r-1] * a[r]
      r -= 2
   k_1 -= 2
   ans1 %= MOD

a.sort(key=abs)

ans2 = 1
for i in a[:k]:
   ans2 *= i
   ans2 %= MOD

if is_minus:
   print(ans2)
else:
   print(ans1)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)



@mt
def slv(N, K, A):
    M = 10**9+7

    def p(N, K, A):
        pa = [a for a in A if a >= 0]
        na = [-a for a in A if a < 0]
        
        pa.sort()
        na.sort()
        ans = 1
        if K % 2 == 1:
            if len(pa) == 0:
                return None
            ans *= pa.pop()
            K -= 1
        for _ in range(K//2):
            if len(pa) >= 2 and len(na) >= 2:
                if pa[-1] * pa[-2] > na[-1] * na[-2]:
                    ans *= pa[-1] * pa[-2]
                    pa.pop()
                    pa.pop()
                else:
                    ans *= na[-1] * na[-2]
                    na.pop()
                    na.pop()
            elif len(pa) >= 2:
                ans *= pa[-1] * pa[-2]
                pa.pop()
                pa.pop()
            elif len(na) >= 2:
                ans *= na[-1] * na[-2]
                na.pop()
                na.pop()
            else:
                break
            ans %= M
        else:
            return ans
        return None

    def n(N, K, A):
        pa = [a for a in A if a >= 0]
        na = [-a for a in A if a < 0]
        
        pa.sort(reverse=True)
        na.sort(reverse=True)
        ans = 1
        for _ in range(K):
            if pa and na:
                if pa < na:
                    ans *= pa[-1]
                    pa.pop()
                else:
                    ans *= -na[-1]
                    na.pop()
            elif pa:
                ans *= pa[-1]
                pa.pop()
            else:
                ans *= -na[-1]
                na.pop()
            ans %= M
        return ans

    a = p(N, K, A)
    if a:
        return a
    return n(N, K, A)


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))

    import random
    
    
    

    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
def prod(A):
    r = 1
    for a in A:
        r *= abs(a)
        r %= mod
    return r

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)

Ak = A[:K]
m = len([a for a in Ak if a<0])

if m%2==0:
    print(prod(Ak))
    exit()

r_p = [a for a in A[K:] if a>=0]
r_n = [a for a in A[K:] if a<=0]
a_p = [a for a in Ak    if a> 0]
a_n_min = max([a for a in Ak if a< 0])

ans1 = ans2 = None
if r_p:
    v1 = abs(a_n_min)
    w1 = max(r_p)
    ans1 = prod(Ak)*pow(v1, mod-2, mod) * w1 % mod
    
if a_p and r_n:
    v2 = min(a_p)
    w2 = abs(min(r_n))
    ans2 = prod(Ak)*pow(v2, mod-2, mod) * w2 % mod
    
if ans1 and ans2:
    print(ans1 if w1*v2>=w2*v1 else ans2)
    exit()

if ans1:
    print(ans1)
    exit()

if ans2:
    print(ans2)
    exit()

print((-prod(A[::-1][:K]))%mod)

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

P = []
M = []
Z = 0
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)
  if i == 0:
    Z += 1

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    if Z != 0:
      print(0)
      exit()
    for i in range(K):
      ans = ans * -M[-1 -i] % MOD
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
elif K<b and d == 0 and K%2 == 1:
    print(0)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % 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
    n -= 1

k //= 2
for _ in range(min(k, n // 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):
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
MOD=10**9+7
plus=[]
minus=[]
zero=[]
for i in range(n):
  if a[i]>0:
    plus.append(a[i])
  if a[i]<0:
    minus.append(a[i])
  if a[i]==0:
    zero.append(a[i])
if k==n:
  ans=1
  for i in range(k):
    ans=(ans*a[i])%MOD
  print(ans)
  sys.exit()
if len(plus)==0:
  if k%2!=0:
    a.reverse()
  ans=1
  for i in range(k):
    ans=(ans*a[i])%MOD
  print(ans)
  sys.exit()
if len(plus)+len(minus)<k:
  print(0)
  sys.exit()
m=len(minus)
minus.sort()
plus.reverse()
plpointer=k
if k>len(plus):
  plpointer=2*(len(plus)//2)
  if k%2==1:
    if plpointer+1<=len(plus):
      plpointer+=1
    else:
      plpointer-=1
mnpointer=k-plpointer
while mnpointer<m-1 and plpointer>=2 and minus[mnpointer]*minus[mnpointer+1]>plus[plpointer-1]*plus[plpointer-2]:
  mnpointer+=2
  plpointer-=2
ans=1
for i in range(mnpointer):
  ans=(ans*minus[i])%MOD
for i in range(plpointer):
  ans=(ans*plus[i])%MOD
print(ans)

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

negs = [-x for x in a if x < 0]
non_negs = [x for x in a if x >= 0]

if len(non_negs) == 0 and k % 2 == 1:
    negs.sort()
    ans = 1
    for i in range(k):
        ans = ans * -negs[i] % MOD
    print(ans)
    exit()

negs_p, non_negs_p = 0, 0

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

for i in range(k):
    if negs_p == len(negs):
        non_negs_p += 1
    elif non_negs_p == len(non_negs):
        negs_p += 1
    elif negs[negs_p] > non_negs[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1

if negs_p % 2 == 0 or k == n:
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if negs_p == len(negs) or non_negs_p == 0:
    negs_p -= 1
    non_negs_p += 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if non_negs_p == len(non_negs) or negs_p == 0:
    negs_p += 1
    non_negs_p -= 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()


a = negs[negs_p - 1]
b = negs[negs_p]
c = non_negs[non_negs_p - 1]
d = non_negs[non_negs_p]

if a * b > c * d:
    negs_p += 1
    non_negs_p -= 1
else:
    negs_p -= 1
    non_negs_p += 1

ans = 1
for i in range(negs_p):
    ans = ans * -negs[i] % MOD
for i in range(non_negs_p):
    ans = ans * non_negs[i] % MOD
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(key=abs, reverse=True)
s = 0
ps = 0
for i in range(k):
    if a[i] < 0:
        s ^= 1
    else:
        ps = 1
b = a[:k]
b.sort(key=abs)
if s:
    p = -MOD
    for i in range(k, n):
        if a[i] >= 0:
            p = a[i]
            break
    q = MOD
    if ps:
        for i in range(k, n):
            if a[i] <= 0:
                q = a[i]
                break
    x = 0
    for j in range(k):
        if b[j] < 0:
            x = b[j]
            xi = j
            break
    y = 0
    for j in range(k):
        if b[j] > 0:
            y = b[j]
            yi = j
            break
    flg = 1
    if y == 0:
        if p >= 0:
            b[xi] = p
            flg = 0
    else:
        if p * y > q * x and p > 0:
            b[xi] = p
        elif q < 0:
            b[yi] = q
        flg = 0
    if flg:
        b = a[-k:]
res = 1
for i in range(k):
    res = res * b[i] % MOD
print(res)

Solution (Python):
from math import log10 as log2

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

mod = 10 ** 9 + 7

p = []
m = []
for a in A :
  if a > 0 :
    p.append(a)
  elif a < 0 :
    m.append(-a)
    
p.sort(reverse=True)
m.sort(reverse=True)
pl = [0]
ml = [0]

for i in range(len(p)) :
  pl.append(log2(p[i]))
for i in range(len(m)) :
  ml.append(log2(m[i]))
for i in range(1, len(pl)) :
  pl[i] += pl[i - 1]
for i in range(1, len(ml)) :
  ml[i] += ml[i - 1]

Mi = -1
Mv = 0
for i in range(0, len(ml), 2) :
  j = K - i
  if len(pl) <= j or j < 0 : continue
  if ml[i] + pl[j] > Mv :
    Mi, Mv = i, ml[i] + pl[j]

if Mi != -1 :
  ret = 1
  for i in range(K - Mi) :
    ret *= p[i]
    ret %= mod
  for i in range(Mi) :
    ret *= m[i]
    ret %= mod
else :
  x = [abs(a) for a in A]
  x.sort()
  ret = 1
  for i in range(K) :
    ret *= x[i]
    ret %= mod
  ret = -ret % mod
  
print(ret)

Solution (Python):
from math import log2
from itertools import accumulate

epsilon = 10 ** -5

MOD = 10 ** 9 + 7

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

negs = []
poss = []
for A in As:
    if A > 0:
        poss.append(A)
    elif A < 0:
        negs.append(-A)

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

if len(poss) + len(negs) < K:
    print(0)
    exit()

if len(poss) == 0:
    if N > len(negs):
        if K % 2 == 1:
            print(0)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    else:
        if K % 2 == 1:
            ans = 1
            for n in negs[-K:]:
                ans *= n
                ans %= MOD
            print(-ans%MOD)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    exit()

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


def mulmod(a, b):
    return a * b % MOD

logs_poss = [0.0] + [log2(p) for p in poss] 
logs_poss_csum = list(accumulate(logs_poss))

poss_mod_csum = [1] + list(accumulate(poss, mulmod))

logs_negs = [0.0] + [log2(n) for n in negs] 
logs_negs_csum = list(accumulate(logs_negs))

negs_mod_csum = [1] + list(accumulate(negs, mulmod))

max_log = -1
for minus in range(0, K+1, 2):
    plus = K - minus
    if plus <= len(poss) and minus <= len(negs):
        if max_log + epsilon < logs_poss_csum[plus] + logs_negs_csum[minus]:
            max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
            max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
        elif max_log <= logs_poss_csum[plus] + logs_negs_csum[minus]:
            mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
            if mod > max_mod:
                max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
                max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD

print(max_mod)