Problem:
 Score : 500 points    Problem Statement Given are N integers A_1,\ldots,A_N .  We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.  Then, print the maximum product modulo (10^9+7) , using an integer between 0 and 10^9+6 (inclusive).      Constraints  1 \leq K \leq N \leq 2\times 10^5  |A_i| \leq 10^9         Input Input is given from Standard Input in the following format:  N  K  A_1  \ldots  A_N       Output Print the maximum product modulo (10^9+7) , using an integer between 0 and 10^9+6 (inclusive).        Sample Input 1 4 2
1 2 -3 -4      Sample Output 1 12  The possible products of the two chosen elements are 2 , -3 , -4 , -6 , -8 , and 12 , so the maximum product is 12 .       Sample Input 2 4 3
-1 -2 -3 -4      Sample Output 2 1000000001  The possible products of the three chosen elements are -24 , -12 , -8 , and -6 , so the maximum product is -6 .  We print this value modulo (10^9+7) , that is, 1000000001 .       Sample Input 3 2 1
-1 1000000000      Sample Output 3 1000000000  The possible products of the one chosen element are -1 and 1000000000 , so the maximum product is 1000000000 .       Sample Input 4 10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1      Sample Output 4 999983200  Be sure to print the product modulo (10^9+7) .

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


mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now*=A[-i-1]%mod
        now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*= mi%mod
        ans%=mod
        l+=2
    else:
        ans*= pl%mod
        ans%=mod
        r-=2
print(ans%mod)

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

mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now= now*A[-i-1]%mod
        
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans= ans*mi%mod
        l+=2
    else:
        ans= ans*pl%mod
        r-=2
print(ans%mod)

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

if K%2==1 and A[-1]<0:
    for i in range(K):
        ans=ans*A[N-(i+1)]%mod
    print(ans)
    exit()

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

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

print(ans)

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, k = map(int, input().split())
    
    
    a = list(map(int, input().split()))
    di = {}
    x = []
    for i in a:
        ab = abs(i)
        x += [ab]
        if ab not in di:
            di[ab] = []
        di[ab] += [1 if i>=0 else -1]

    x = sorted(x, reverse=True)
    signs = []
    for each in x:
        signs += [di[each].pop()]

    cursign = 1
    ans = 1
    firstpos = -1
    firstneg = 0
    nextpos = None
    nextneg = None
    for i in range(k):
        ans = (ans * x[i]) % (10**9+7)
        cursign *= signs[i]
        if signs[i] == 1:
            firstpos = i
        if signs[i] == -1:
            firstneg = i

    if cursign == 1:
        print(ans)
        quit()

    for i in range(k, len(x)):
        if signs[i] == 1 and nextpos is None:
            nextpos = i
        if signs[i] == -1 and nextneg is None:
            nextneg = i
    ansdex = [i for i in range(k)]
    from math import inf
    ans = ans*-1
    
    
    ans1, ans2 = -10**18, -10**18
    if nextpos is not None:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstneg] = nextpos
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10**9+7)
        ans2 = ans22

    if nextneg is not None and firstpos != -1:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstpos] = nextneg
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10 ** 9 + 7)
        ans1 = ans22
    if ans1 != -10**18 and ans2 != -10**18:
        print(ans1 if x[nextneg]/x[firstpos] > x[nextpos]/x[firstneg] else ans2 if x[nextneg]/x[firstpos] < x[nextpos]/x[firstneg] else max(ans1, ans2))
        quit()
    if ans1 != -10**18 or ans2 != -10**18:
        print(max(ans1, ans2))
        quit()

    a = sorted(a, reverse=True)
    ans=1
    for i in range(k):ans=(ans*(a[i])) % (10**9+7)
    print(ans)

Solution (Python):
from collections import defaultdict
def prod(A,k,mod):
  ans = 1
  for i in range(k):
      ans *= A[i]
      ans %= mod
  return ans
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  ans = 1
  if K==N:
    return prod(A,N,mod)
  minus = len([a for a in A if a<0])
  if minus==N:
    if K%2==0:
      A.sort()
    else:
      A.sort(reverse=True)
    return prod(A,K,mod)
  if K==1:
    return max(A)
  A.sort(key=lambda x:-abs(x))
  if A[K]==0:
    return 0
  minus = len([a for a in A[:K] if a<0])
  flag = [1]*K+[0]*(N-K)
  d = defaultdict(lambda: -1)
  if minus%2==1:
    for i in range(K,N):
      if A[i]>=0:
        d['p2'] = i
        break
    for i in range(K,N):
      if A[i]<0:
        d['m2'] = i
        break
    for i in range(K-1,-1,-1):
      if A[i]>0:
        d['p1'] = i
        break
    for i in range(K-1,-1,-1):
      if A[i]<0:
        d['m1'] = i
        break
    if d['p2']==-1 or d['m1']==-1:
      flag[d['m2']],flag[d['p1']] = 1,0
    elif d['m2']==-1 or d['p1']==-1:
      flag[d['p2']],flag[d['m1']] = 1,0
    elif A[d['p2']]*A[d['p1']]>A[d['m1']]*A[d['m2']]:
        flag[d['p2']],flag[d['m1']] = 1,0
    else:
      flag[d['m2']],flag[d['p1']] = 1,0
    ans = 1
    for i in range(N):
      if flag[i]==1:
        ans *= A[i]
        ans %= mod
    return ans
  return prod(A,K,mod)
print(solve())

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

import sys
input = sys.stdin.buffer.readline

def main():

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

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

    flag = True
    if len(PZ) > 0:
        if n == k:
            if len(N)%2 != 0:
                flag = False
    else:
        if k%2 != 0:
            flag = False

    if flag:
        if k%2 == 0:
            PZ.sort(reverse=True)
            N.sort()
            s = len(PZ)
            t = len(N)
            C = []
            for i in range(s//2):
                C.append(PZ[2*i]*PZ[2*i+1])
            for i in range(t//2):
                C.append(N[2*i]*N[2*i+1])
            C.sort(reverse=True)
            ans = 1
            for i in range(k//2):
                ans *= C[i]
                ans %= mod
        else:
            PZ.sort()
            ans = PZ.pop()
            PZ.reverse()
            N.sort()
            s = len(PZ)
            t = len(N)
            C = []
            for i in range(s//2):
                C.append(PZ[2*i]*PZ[2*i+1])
            for i in range(t//2):
                C.append(N[2*i]*N[2*i+1])
            C.sort(reverse=True)
            for i in range(k//2):
                ans *= C[i]
                ans %= mod
    else:
        ABS = [abs(a) for a in A]
        ABS.sort()
        ans = 1
        for i in range(k):
            ans *= ABS[i]
            ans %= mod
        ans *= -1
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

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

import sys
input = sys.stdin.buffer.readline

def main():

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

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

    flag = True
    if len(PZ) > 0:
        if n == k:
            if len(N)%2 != 0:
                flag = False
    else:
        if k%2 != 0:
            flag = False

    if flag:
        if k%2 == 0:
            PZ.sort(reverse=True)
            N.sort()
            s = len(PZ)
            t = len(N)
            C = []
            for i in range(s//2):
                C.append(PZ[2*i]*PZ[2*i+1])
            for i in range(t//2):
                C.append(N[2*i]*N[2*i+1])
            C.sort(reverse=True)
            ans = 1
            for i in range(k//2):
                ans *= C[i]
                ans %= mod
        else:
            PZ.sort()
            ans = PZ.pop()
            PZ.reverse()
            N.sort()
            s = len(PZ)
            t = len(N)
            C = []
            for i in range(s//2):
                C.append(PZ[2*i]*PZ[2*i+1])
            for i in range(t//2):
                C.append(N[2*i]*N[2*i+1])
            C.sort(reverse=True)
            for i in range(k//2):
                ans *= C[i]
                ans %= mod
    else:
        ABS = [abs(a) for a in A]
        ABS.sort()
        ans = 1
        for i in range(k):
            ans *= ABS[i]
            ans %= mod
        ans *= -1
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def func(A, n, k): 
    A.sort() 
    product = 1

    if (A[n - 1] == 0 and (k & 1)): 
        return 0

    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k - 1, -1): 
            product = (product*A[i])%mod
        return product 

    i = 0
    j = n - 1
    if (k & 1): 
        product = (product*A[j])%mod 
        j-= 1
        k-=1

    k >>= 1
  
    for itr in range( k) : 
        left_product = A[i] * A[i + 1] 
 
        right_product = A[j] * A[j - 1] 
  
        if (left_product > right_product) : 
            product = (product*(left_product%mod))%mod
            i += 2
          
        else : 
            product = (product*(right_product%mod))%mod
            j -= 2
  
    return product 


n,k=map(int,input().split())
arr=list(map(int,input().split()))
global mod
mod=1000000007
ans=func(arr,n,k)
print(ans%mod)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
div=7+10**9
ans=1
t=0
i,j=0,N-1

if A[-1]<0 and K%2==1:
    for i1 in range(N-K,N):
        ans*=A[i1]
        ans%=div
else:
    while t<K-1:
        if A[i]*A[i+1]>A[j]*A[j-1]:
            ans*=A[i]*A[i+1]
            ans%=div
            i+=2
            t+=2
        else:
            ans*=A[j]
            ans%=div
            j+=-1
            t+=1
    if t==K-1:
        ans*=A[j]
        ans%=div

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
zero = 0
for i in range(n):
    if a[i] >= 0:
        if a[i] == 0:
            zero += 1
        a[i] = [a[i], 1]
    else:
        a[i] = [-a[i], 0]
        neg += 1
a.sort(reverse = True)
ans = 1
if n == k:
    for i in range(n):
        ans *= a[i][0]
        ans %= mod
        if not a[i][1]:
            ans *= -1
            ans %= mod
elif k % 2 == 1 and (neg == n or neg + zero == n):
    for i in range(1, k + 1):
        ans *= -a[-i][0]
        ans %= mod
else:
    pos, neg = 0, 0
    lastpos, lastneg = mod, mod
    for i in range(k):
        ans *= a[i][0]
        ans %= mod
        if a[i][1]:
            pos += 1
            lastpos = a[i][0]
        else:
            neg += 1
            lastneg = a[i][0]
    if neg % 2 == 1:
        firstpos, firstneg = mod, mod
        for i in range(k, n):
            if not firstpos == mod and not firstneg == mod:
                break
            if firstpos == mod and a[i][1]:
                firstpos = a[i][0]
            elif firstneg == mod and not a[i][1]:
                firstneg = a[i][0]
        if not mod in [lastpos, lastneg, firstpos, firstneg]:
            if firstpos * lastpos >= firstneg * lastneg:
                ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
            else:
                ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastpos, firstneg]:
            ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastneg, firstpos]:
            ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
print(ans)

Solution (Python):
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

array = []
if K%2 == 1:
    array.append(plus.pop(0))
    l_plus -= 1
    K -= 1
m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
\
while counter * 2 + 1 < K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1
 
    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1

result = 1
for each in array:
    result = result * each % M
print(result)

Solution (Python):
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    count = 0
    while True:
        if count == k:
            break
        elif count == k - 1:
            ans *= a_list[r] % mod
            ans %= mod
            break
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            count += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= a_list[r] % mod
            r -= 1
            count += 1
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod
print(ans)

Solution (Python):
def sgn(x):
    if x>0:
        return 1
    elif x<0:
        return -1
    else:
        return 0
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1:
    ans=1
    A.sort()
    for i in range(K):
        ans=ans*A[-i-1]
        ans%=mod
    print(ans)
    exit()
A.sort(key=lambda x:abs(x),reverse=True)
P=1
Pfugou=1
for i in range(K):
    P=P*A[i]
    P%=mod
    Pfugou=Pfugou*sgn(A[i])
if Pfugou!=-1:
    print(P)
    exit()
X=[]
Y=[]
for i in range(N):
    if A[i]>=0:
        X.append(A[i])
    else:
        Y.append(-A[i])
X.sort()
Y.sort()
S=[]
while(len(S)<K):
    if len(S)==K-1:
        S.append(X[-1])
        X.pop()
    elif len(X)<=1 and len(Y)<=1:
        
        
        
        
        
        
        pass
    elif len(X)<=1:
        S.append(Y[-1])
        S.append(Y[-2])
        Y.pop()
        Y.pop()
    elif len(Y)<=1:
        S.append(X[-1])
        S.append(X[-2])
        X.pop()
        X.pop()
    else:
        if X[-1]*X[-2]>Y[-1]*Y[-2]:
            S.append(X[-1])
            X.pop()
        else:
            S.append(Y[-1])
            S.append(Y[-2])
            Y.pop()
            Y.pop()
ans=1
for i in S:
    ans=ans*i
    ans%=mod
print(ans)

Solution (Python):
MOD = 10**9 + 7
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])

B = []
plus, zero, minus = 0, 0, 0
for i in range(N):
    if A[i] >= 0:
        B.append((A[i], 1))
        plus += 1
    elif A[i] == 0:
        B.append((0, 0))
        zero += 1
    else:
        B.append((-A[i], -1))
        minus += 1


if plus >= K-(min(K, minus)//2*2):
    B = sorted(B, key=lambda x: x[0], reverse=True)

    c = 1
    for i in range(K):
        c *= B[i][1]

    if c == 1:
        ans = 1
        for i in range(K):
            ans *= B[i][0]
            ans %= MOD

    else:
        ap, an = 1, 1
        skip = []
        for i in range(K-1, -1, -1):
            if B[i][1] == 1:
                ap *= B[i][0]
                skip.append(i)
                break
        else:
            skip.append(K-1)
            an = 0
        for i in range(K-1, -1, -1):
            if B[i][1] == -1:
                an *= B[i][0]
                skip.append(i)
                break
        else:
            skip.append(K-1)
            ap = 0
        for i in range(K, N):
            if B[i][1] == 1:
                ap *= B[i][0]
                break
        for i in range(K, N):
            if B[i][1] == -1:
                an *= B[i][0]
                break
        a = max(ap, an)

        ans = 1
        for i in range(K):
            if i not in skip:
                ans *= B[i][0]
                ans %= MOD
        ans *= a
        ans %= MOD

elif zero >= K-(min(K, minus)//2*2):
    print(0)
    exit()

else:
    B = sorted(B, key=lambda x: x[0], reverse=False)
    ans = 1
    for i in range(K):
        ans *= B[i][0]*B[i][1]
        ans %= MOD

print(ans)

Solution (Python):
mod=1000000007
n,k=map(int, input().split())
lst=list(map(int, input().split()))
lst=sorted(lst)
p=1
if lst[-1]==0 and k%2!=0:
    print(0)
elif lst[-1]<0 and k%2!=0:
    for i in range(n-1,n-k-1,-1):
        
        p=(p%mod*lst[i]%mod)%mod
    
    print(p%mod)
else:
    j=n-1
    if k%2!=0:
        p*=lst[j]
        k-=1
        j-=1
    k=k//2
    i=0
    for x in range(k):
        if lst[i]*lst[i+1]>lst[j]*lst[j-1]:
            p=(p%mod*lst[i]%mod*lst[i+1]%mod)%mod
            i+=2
        else:
            p=(p%mod*lst[j]%mod*lst[j-1]%mod)%mod
            j-=2
    
    print(p%mod)

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

def main():
  A_posi = []
  A_nega = []
  for a in A:
    if a > 0:
      A_posi.append(a)
    elif a < 0:
      A_nega.append(-a)

  len_posi = len(A_posi)
  len_nega = len(A_nega)
  
  if len_posi + len_nega < K:
    return 0

  if (len_nega % 2 == 1 and K == len_posi + len_nega) or (K % 2 == 1 and len_posi == 0):
    if len_posi + len_nega == N:
      A_posi.sort()
      A_nega.sort()
      answer = 1
      k = 0
      for a in A_nega:
        answer *= (- a) % DE
        answer %= DE
        k += 1
        if k >= K:
          break
      else:
        for a in A_posi:
          answer *= a % DE
          answer %= DE
          k += 1
          if k >= K:
            break
      return answer
    else:
      return 0
  A_posi.sort(reverse=True)
  A_nega.sort(reverse=True)
  posi = 0
  nega = 0
  answer = 1

  if K % 2 == 1:
    answer = A_posi[0] % DE
    posi = 1

  while posi + nega + 2 <= K:
    p = A_posi[posi] * A_posi[posi + 1] if posi + 1 < len_posi else 0
    n = A_nega[nega] * A_nega[nega + 1] if nega + 1 < len_nega else 0
    if p > n:
      answer *= p % DE
      answer %= DE
      posi += 2
    else:
      answer *= n % DE
      answer %= DE
      nega += 2

  return answer

print(main())

Solution (Python):
"""
9 5
-4 -3 -2 -1 0 1 2 3
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
Am = []
Ap = []
for a in A:
    if a < 0:
        Am.append(a)
    else:
        Ap.append(a)

mod = 10**9 + 7

ans = 1

if N == K:
    for a in A:
        ans *= a
        ans %= mod

elif A[-1] < 0:
    if K % 2 == 1:
        for i in range(K):
            ans *= Am[-1-i]
            ans %= mod
    else:
        for i in range(K):
            ans *= Am[i]
            ans %= mod

else:
    if K%2 == 1:
        ans *= Ap[-1]
        ans %= mod
        K -= 1
        del Ap[-1]
    Amd = []     
    Apd = []
    for i in range(len(Ap)//2):
        Apd.append(Ap[-1-(2*i)]*Ap[-1-(2*i+1)])
    for i in range(len(Am)//2):
        Amd.append(Am[2*i]*Am[2*i+1])
    Apd.append(-1)
    Amd.append(-1)
    
    ip = 0
    im = 0
    while K > 0:
        if Apd[ip] >= Amd[im]:
            ans *= Apd[ip]
            ip += 1
        else:
            ans *= Amd[im]
            im += 1
        ans %= mod
        K -= 2


ans %= mod
print(ans)

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

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

neg = []
zero = 0
pos = []
for a in A:
    if a < 0:
        neg.append(a)
    else:
        pos.append(a)

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

if len(pos) == 0:
    res = 1
    if K % 2 == 0:
        neg.reverse()
    for a in neg[:K]:
        res *= a
        res %= mod
else:
    res = 1
    if K % 2 == 1:
        res = pos.pop()
        K -= 1
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            res *= pos.pop()
            res %= mod
            res *= pos.pop()
            res %= mod
        else:
            res *= neg.pop()
            res %= mod
            res *= neg.pop()
            res %= mod
        K -= 2
    while K > 1 and len(pos) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K > 1 and len(neg) > 1:
        res *= neg.pop()
        res %= mod
        res *= neg.pop()
        res %= mod
        K -= 2
    while K and pos:
        res *= pos.pop()
        res %= mod
        K -= 1
    while K and neg:
        res *= neg.pop()
        res %= mod
        K -= 1


print(res)

Solution (Python):
from copy import deepcopy
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
ans = 1
i, j = 0, n - 1
k2 = deepcopy(k)
while k2 > 1:
    if a[i] * a[i + 1] > a[j] * a[j - 1]:
        ans *= a[i] * a[i + 1]
        ans %= mod
        i += 2
        k2 -= 2
    else:
        ans *= a[j]
        j -= 1
        ans %= mod
        k2 -= 1
if k2 == 1:
    ans *= a[j]
    ans %= mod
if a[-1] < 0 and k % 2:
    ans = 1
    for i in range(n - k, n):
        ans *= a[i]
        ans %= mod
print(ans)

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

n,k=map(int, input().split())
a=list(map(int, input().split()))
aplus,aminus=[],[]

for i in range(n):
    if a[i] >= 0: aplus.append(a[i])
    else: aminus.append(a[i])

      
if len(aplus) == 0 and k % 2 == 1:
    asort = sorted(a,reverse=True)
    ans = 1
    for i in range(k):
        ans = (ans * asort[i]) % MOD
    print(ans)
    exit()

if n == k:
    ans = 1
    for i in range(k):
        ans = (ans * a[i]) % MOD
    print(ans)
    exit()

newa = sorted(a,reverse=True,key=abs)
newaplus = sorted(aplus,reverse = True)
newaminus = sorted(aminus)

cntp,cntm,pp,mm=0,0,0,0

for i in range(k):
    if newa[i] >= 0:
        cntp += 1
        pp = i
    else:
        cntm += 1
        mm = i

if cntm % 2 == 1:
    if cntp == 0:
        newa[mm] = newaplus[cntp]
    elif len(newaplus) == cntp:
        newa[pp] = newaminus[cntm]
    elif len(newaminus) == cntm:
        newa[mm] = newaplus[cntp]
    else:
        if newa[pp] * newaplus[cntp] >= newa[mm] * newaminus[cntm]:
            newa[mm] = newaplus[cntp]
        else:
            newa[pp] = newaminus[cntm]

ans = 1
for i in range(k):
    ans = (ans * newa[i]) % MOD
    
print(ans)

Solution (Python):
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()

if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()

if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)

ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

Solution (Python):
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1

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

if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()

if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)

ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

Solution (Python):
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1

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

if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()

if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)

ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

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

if k == n:
    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)
    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()
minus.sort(reverse=True)
while k > 0:
    if len(plus) >= 2 and len(minus) >= 2:
        nump = plus[-1] * plus[-2]
        numm = minus[-1] * minus[-2]
        if nump > numm or k == 1:
            ans *= plus.pop()
            ans %= mod
            k -= 1
        else:
            ans *= minus.pop()
            ans *= minus.pop()
            ans %= mod
            k -= 2
    elif len(minus) < 2:
        ans *= plus.pop()
        ans %= mod
        k -= 1
    elif len(plus) < 2:
        if k%2 == 0:
            ans *= minus.pop()
            ans *= minus.pop()
            ans %= mod
            k -= 2
        else:
            ans *= plus.pop()
            ans %= mod
            k -= 1
print(ans)

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

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

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)