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 = list(map(int,input().split()))
MOD = 1000000007

arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minuscount = 0
minusposition = 0

def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)
 
arr = sorted(A,reverse = True)
if arr[(N -1)] > 0 :
    for i in range(K):
        seki = seki * arr[i] % MOD
else:
    if arr[0] < 0 :
        for j in range(K):
            if K % 2 == 1:
                seki = seki * arr[j] % MOD
            else:
                seki = seki * arr[N-j-1] % MOD
    else:
        while (i + j) < K:
            if (i + j + 1) < K :
                if arr[i] * arr[i+1] > (arr[(N - j -1)] * arr[(N - j -2)]):
                    seki = seki * arr[i] % MOD
                    i += 1
                else:
                    minuscount += 2
                    minusposition = N - j -2
                    seki = (seki * arr[(N - j -1)] % MOD) * arr[(N - j -2)] % MOD
                    j += 2
            else:
                if abs(arr[i]) > abs( arr[(N - j -1)]) :
                    seki = seki * arr[i] % MOD
                    i += 1
                else:               
                    minuscount += 1
                    minusposition = N - j -1
                    seki = seki * arr[(N - j -1)] % MOD
                    j += 1
if (minuscount % 2) != 0:
    if minusposition != (i - 1):
        gyaku = modinv(arr[minusposition],MOD)
        seki  = seki * gyaku % MOD
        seki  = seki * arr[i] % MOD
print(seki)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
mul = lambda x, y : x * y % MOD
from functools import reduce
def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(key = abs, reverse = 1)

    if all(a < 0 for a in A) or n == k:
        if k & 1:
            print(reduce(mul, A[-k:]))
        else:
            print(reduce(mul, A[:k]))
        return

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

    pos.reverse()
    neg.reverse()
    ans = 1
    if k & 1:
        ans *= pos.pop()
        k -= 1

    for _ in range(k // 2):
        if len(pos) >= 2 and len(neg) >= 2:
            a, b = pos[-2:]
            c, d = neg[-2:]
            if a * b >= c * d:
                ans *= pos.pop()
                ans *= pos.pop()
                ans %= MOD
            else:
                ans *= neg.pop()
                ans *= neg.pop()
                ans %= MOD
        elif len(pos) >= 2:
            ans *= pos.pop()
            ans *= pos.pop()
            ans %= MOD
        elif len(neg) >= 2:
            ans *= neg.pop()
            ans *= neg.pop()
            ans %= MOD
    print(ans)
resolve()

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

import numpy as np

x = np.argsort(list(map(lambda x: -abs(x), A)))
B = []
C = []

for xx in x:
    B.append(A[xx])
    C.append(np.sign(A[xx]))

ans = 1
s = 1
flag4 = 0

for i in range(K):
    s *= C[i]

if s < 0:
    p = np.sign(B[K-1])
    flag1 = 0
    for i in range(K-1,-1,-1):
        if C[i] == p*(-1):
            idx1 = i
            flag1 = 1
            break

    flag2 = 0
    for i in range(K,N):
        if C[i] == p*(-1):
            idx2 = i
            flag2 = 1
            break

    flag3 = 0
    if flag1 == 1:
        for i in range(K,N):
            if C[i] == p:
                idx3 = i
                flag3 = 1
                break

    if flag1 and flag2 and flag3:
        if abs(B[K-1])*abs(B[idx3]) <= abs(B[idx1])*abs(B[idx2]):
            B[K-1] = B[idx2]
        else:
            B[idx1] = B[idx3]
    elif flag1 and (not flag2) and flag3:
        B[idx1] = B[idx3]
    elif flag1 and flag2 and (not flag3):
        B[K-1] = B[idx2]
    elif (not flag1) and flag2:
        B[K-1] = B[idx2]
    else:
        flag4 = 1

if flag4:
    for i in range(N-1,N-K-1,-1):
        ans = (ans * (B[i] % mod)) % mod
else:
    for i in range(K):
        ans = (ans * (B[i] % mod)) % mod

print(ans % mod)

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

MOD = 10**9+7
N, K = map(int, readline().split())
A = list(map(int, readline().split()))
posi = [(a, 0) for a in A if a >= 0]
nega = [(-a, 1) for a in A if a < 0]
B = posi + nega
B.sort(reverse = True)

if N == K:
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD  
    print(ans)
elif N == len(nega):
    if K & 1:
        A.sort(reverse = True)
    else:
        A.sort()
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD  
    print(ans)
else:
    cnt = 0
    for i in range(K):
        _, s = B[i]
        cnt ^= s
    
    res, _ = map(list, zip(*B[:K]))
    if cnt:
        pf, nf, ps, ns = None, None, 0, 0
        for i in range(K):
            b, s = B[i]
            if s:
                nf = b
            else:
                pf = b
        
        for i in range(K, N):
            b, s = B[i]
            if s:
                ns = b
                break
        for i in range(K, N):
            b, s = B[i]
            if not s:
                ps = b
                break
        
        if pf is None:
            res.remove(nf)
            res.append(ps)
        elif nf is None:
            res.remove(pf)
            res.append(ns)
        elif ns*nf >= pf*ps:
            res.remove(pf)
            res.append(ns)
        else:
            res.remove(nf)
            res.append(ps)
        
    ans = 1
    for r in res:
        ans = (ans*r) % MOD
        
    print(ans)

Solution (Python):

import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    A_list.sort(key=lambda x: -abs(x))
    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)
    

    ans = 1
    cnt = 0
    i_p = 0  
    i_m = 0  


    while (cnt < K):
        if (K - cnt) == 1:
            if i_p < len(A_plus):
                ans *= A_plus[i_p]
                ans %= mod
                cnt += 1
                i_p += 1
                break
            
            else:
                ans2 = 1

                for i in range( len(A_list)-K, len(A_list) ):
                    ans2 *= A_list[i]
                    ans2 %= mod

                print(ans2)
                return


        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    ans *= A_plus[i_p]
                    cnt += 1
                    i_p += 1
                else:
                    ans *= (A_minus[i_m] * A_minus[i_m + 1])
                    cnt += 2
                    i_m += 2

            else:
                ans *= (A_minus[i_m] * A_minus[i_m + 1])
                cnt += 2
                i_m += 2
            
        else:
            ans *= A_plus[i_p]
            cnt += 1
            i_p += 1
        

        ans %= mod
    
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Solution (Python):

import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    A_list.sort(key=lambda x: -abs(x))
    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)
    

    select = []
    i_p = 0  
    i_m = 0  

    
    while (len(select) < K):
        if (K - len(select)) == 1:
            if i_p < len(A_plus):
                select.append( A_plus[i_p] )
                i_p += 1
                break
            
            else:
                ans = 1

                for i in range( len(A_list)-K, len(A_list) ):
                    ans *= A_list[i]
                    ans %= mod

                print(ans)
                return


        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    select.append( A_plus[i_p] )
                    i_p += 1
                else:
                    select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                    i_m += 2

            else:
                select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                i_m += 2
            
        else:
            select.append( A_plus[i_p] )
            i_p += 1
    


    ans = 1
 
    for i in range(K):
        ans *= select[i]
        ans %= mod
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):

import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    A_list.sort(key=lambda x: -abs(x))
    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)
    

    if (not A_plus):
        if (K % 2 == 0):
            target_range = range(K)
        else:
            target_range = range(len(A_minus)-K, len(A_minus))

        ans = 1

        for i in target_range:
            ans *= A_minus[i]
            ans %= mod
        
        print(ans)
        return


    if (not A_minus):
        ans = 1

        for i in range(K):
            ans *= A_plus[i]
            ans %= mod
        
        print(ans)
        return


    select = []
    i_p = 0  
    i_m = 0  


    while (len(select) < K):
        if (K - len(select)) == 1:
            if i_p < len(A_plus):
                select.append( A_plus[i_p] )
                i_p += 1
                break
            
            else:
                ans = 1

                for i in range( len(A_list)-K, len(A_list) ):
                    ans *= A_list[i]
                    ans %= mod

                print(ans)
                return


        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    select.append( A_plus[i_p] )
                    i_p += 1
                else:
                    select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                    i_m += 2

            else:
                select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                i_m += 2
            
        else:
            select.append( A_plus[i_p] )
            i_p += 1
    

    ans = 1
 
    for i in range(K):
        ans *= select[i]
        ans %= mod
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Solution (Python):

import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))


    A_list.sort(key=lambda x: -abs(x))
    mod = 10**9 + 7

    L_plus  = R_plus  = -1 
    L_minus = R_minus = -1 
    
    


    for i in range(K-1, -1, -1):
        if (L_plus == -1) and (A_list[i] >= 0):
            L_plus = i
        if (L_minus == -1) and (A_list[i] < 0):
            L_minus = i
        if (L_plus != -1) and (L_minus != -1):
            break
    
    for i in range(K,N):
        if (R_plus == -1) and (A_list[i] >= 0):
            R_plus = i
        if (R_minus == -1) and (A_list[i] < 0):
            R_minus = i
        if (R_plus != -1) and (R_minus != -1):
            break


    cnt_minus = 0

    for i in range(K):
        if A_list[i] < 0:
            cnt_minus += 1


    if cnt_minus % 2 == 0:
        target_idx = [0, K-1]
    
    else: 
        if (R_plus == -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = calc2 = 0
        
        elif (R_plus != -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = 1
            calc2 = 0
        
        elif (R_plus == -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
        
            calc1 = 0
            calc2 = 1
        
        elif (R_plus != -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
            
            calc1 = A_list[L_plus] * A_list[R_plus]
            calc2 = A_list[L_minus] * A_list[R_minus]


        if calc1 == calc2:
            target_idx = [N-K, N-1]
        
        elif calc1 > calc2:
            A_list[L_minus], A_list[R_plus] = A_list[R_plus], A_list[L_minus]
            target_idx = [0, K-1]

        elif calc1 < calc2:
            A_list[L_plus], A_list[R_minus] = A_list[R_minus], A_list[L_plus]
            target_idx = [0, K-1]


    ans = 1

    for i in range( target_idx[0], (target_idx[1] + 1) ):
        ans *= A_list[i]
        ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))


    A_list.sort(key=lambda x: -abs(x))
    mod = 10**9 + 7

    L_plus  = R_plus  = -1 
    L_minus = R_minus = -1 
    
    


    for i in range(K-1, -1, -1):
        if (L_plus == -1) and (A_list[i] >= 0):
            L_plus = i
        if (L_minus == -1) and (A_list[i] < 0):
            L_minus = i
        if (L_plus != -1) and (L_minus != -1):
            break
    
    for i in range(K,N):
        if (R_plus == -1) and (A_list[i] >= 0):
            R_plus = i
        if (R_minus == -1) and (A_list[i] < 0):
            R_minus = i
        if (R_plus != -1) and (R_minus != -1):
            break


    cnt_minus = 0

    for i in range(K):
        if A_list[i] < 0:
            cnt_minus += 1


    if cnt_minus % 2 == 0:
        target = A_list[:K]
    
    else: 
        if (R_plus == -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = calc2 = 0
        
        elif (R_plus != -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = 1
            calc2 = 0
        
        elif (R_plus == -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
        
            calc1 = 0
            calc2 = 1
        
        elif (R_plus != -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
            
            calc1 = A_list[L_plus] * A_list[R_plus]
            calc2 = A_list[L_minus] * A_list[R_minus]


        if calc1 == calc2:
            target = A_list[N-K:N]
        
        elif calc1 > calc2:
            A_list[L_minus], A_list[R_plus] = A_list[R_plus], A_list[L_minus]
            target = A_list[:K]

        elif calc1 < calc2:
            A_list[L_plus], A_list[R_minus] = A_list[R_minus], A_list[L_plus]
            target = A_list[:K]


    ans = 1

    for i in range(len(target)):
        ans *= target[i]
        ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

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

X = sorted([a for a in A if a >= 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))
ans = 1

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

else:
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD

print(ans)

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

X = sorted([a for a in A if a >= 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    ans = 1
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

    print(ans)

else:
    ans = 1
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD
    print(ans)

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

X = sorted([a for a in A if a > 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    ans = 1
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

    print(ans)

elif 0 in A:
    print(0)

else:
    ans = 1
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD
    print(ans)

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):
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0:
    if K%2:
        if 0 in A:
            ans = 0
        else:
            ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    else:
        ans = reduce(lambda a, b: a*b%mod, Am[:K], 1)
    print(ans)
    exit()

idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and idx_Ap > 0 and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Solution (Python):

def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    if lastA == -1 or (firstA is not None and A[K][0]/A[lastA][0] < A[firstA][0]/A[K-1][0]):
        res = prod(A[:K - 1]) * A[firstA][0]
    else:
        res = prod(A[:lastA]) * prod(A[lastA + 1:K + 1])
print(res%MOD)
"""
6 3
5 -3 -3 -3 -3 -2

10 7
-10 -10 -10 -10 10 10 10 10 10 10
"""

Solution (Python):
import sys

mod = 10**9+7

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

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

det = -1
for i in range(K):
    if A[i] >= 0:
        det = 1
        break

if det == -1 and K%2 == 1:
    value = 1
    A.sort(reverse = True)
    for i in range(K):
        value *= A[i]
        value %= mod
    print(value)
    sys.exit(0)

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






value = 1
sgn = 1
for i in range(K):
    value *= A[i]
    value %= mod
    if A[i] < 0:
        sgn *= -1
    elif A[i] == 0:
        sgn = 0



if N==K:
    print(value)

elif sgn >=0:
    print(value)
else:
    

    X = ['','']
    num = K
    while (X[0] == '' or X[1] == '') and num > 0:
        
        num -= 1
        if A[num] > 0 and X[0] == '':
            X[0] = A[num]
        elif A[num] < 0 and X[1] == '':
            X[1] = A[num]
        
        
        
    
    Y = ['','']
    
    
    num = K-1
    while (Y[0] == '' or Y[1] == '') and num < N-1:
        num += 1
        if A[num] > 0 and Y[0] == '':
            Y[0] = A[num]
        elif A[num] < 0 and Y[1] == '':
            Y[1] = A[num]
    
    
    

    if X[0] != '' and X[1] != '' and Y[0] != '' and Y[1] != '':
        if abs(X[0]*Y[0]) >= abs(X[1]*Y[1]):
            value *= Y[0]
            value *= pow(X[1],mod-2,mod)
            value %= mod
            print(value)
        else:
            value *= Y[1]
            value *= pow(X[0],mod-2,mod)
            value %= mod
            print(value)

    elif X[1] != '' and Y[0] != '':
        value *= Y[0]
        value *= pow(X[1],mod-2,mod)
        value %= mod
        print(value)
    
    else:
        value *= Y[1]
        value *= pow(X[0],mod-2,mod)
        value %= mod
        print(value)

Solution (Python):
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    if lastA == -1 or (firstA is not None and A[K][0]/A[lastA][0] < A[firstA][0]/A[K-1][0]):
        res = prod(A[:K - 1]) * A[firstA][0]
    else:
        res = prod(A[:lastA]) * prod(A[lastA + 1:K + 1])
print(res%MOD)
"""
6 3
5 -3 -3 -3 -3 -2

10 7
-10 -10 -10 -10 10 10 10 10 10 10
"""

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=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):
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u


n, k = map(int, input().split())
al = list(map(int, input().split()))
al_abs = []
al_p = []
al_m = []
zero_cnt = 0
MOD = 10**9+7

for a in al:
    if a == 0:
        zero_cnt+=1
    elif a > 0: 
        al_abs.append((abs(a),1))
        al_p.append(a)
    else: 
        al_abs.append((abs(a),-1))
al_abs.sort(reverse=True)


if n == k:
    ans = 1
    for a in al:
        ans *= a
        ans %= MOD
    print(ans)
    exit()


if len(al_abs) < k:
    print(0)
    exit()



if not al_p:
    if k%2 == 1 and zero_cnt > 0:
        print(0)
    else:
        if k%2 == 1:
            al_abs.sort()
        ans = 1
        for a,s in al_abs[:k]:
            ans *= (a*(-1))
            ans %= MOD
        print(ans)
    exit()


val = 1
m_cnt = 0
last_m = 0
last_p = 0
for i in range(k):
    v,sig = al_abs[i]
    val *= v
    val %= MOD
    if sig == -1:
        m_cnt += 1
        last_m = v
    else:
        last_p = v

if m_cnt %2 == 0:
    print(val)
    exit()





next_p = 0
for i in range(k,len(al_abs)):
    v,sig = al_abs[i]
    if sig == 1:
        next_p = v
        break


next_m = 0
for i in range(k,len(al_abs)):
    v,sig = al_abs[i]
    if sig == -1:
        next_m = v
        break

if next_p == 0 and next_m == 0:
    print(0)
    exit()


if next_p*last_p >= next_m*last_m or last_p == 0:
    ans = val*modinv(last_m%MOD,MOD)*next_p
    ans %= MOD
    print(ans)

else:
    ans = val*modinv(last_p%MOD,MOD)*next_m
    ans %= MOD
    print(ans)

Solution (Python):
n, k = map(int, input().split())
al = list(map(int, input().split()))
al_abs = []
al_p = []
al_m = []
zero_cnt = 0
MOD = 10**9+7

for a in al:
    if a == 0:
        zero_cnt+=1
    elif a > 0: 
        al_abs.append((abs(a),1))
        al_p.append(a)
    else: 
        al_abs.append((abs(a),-1))
al_abs.sort(reverse=True)


if n == k:
    ans = 1
    for a in al:
        ans *= a
        ans %= MOD
    print(ans)
    exit()


if len(al_abs) < k:
    print(0)
    exit()



if not al_p:
    if k%2 == 1 and zero_cnt > 0:
        print(0)
    else:
        if k%2 == 1:
            al_abs.sort()
        ans = 1
        for a,s in al_abs[:k]:
            ans *= (a*(-1))
            ans %= MOD
        print(ans)
    exit()


val = 1
m_cnt = 0
last_m = 0
last_p = 0
for i in range(k):
    v,sig = al_abs[i]
    val *= v
    val %= MOD
    if sig == -1:
        m_cnt += 1
        last_m = v
    else:
        last_p = v

if m_cnt %2 == 0:
    print(val)
    exit()





next_p = 0
for i in range(k,len(al_abs)):
    v,sig = al_abs[i]
    if sig == 1:
        next_p = v
        break


next_m = 0
for i in range(k,len(al_abs)):
    v,sig = al_abs[i]
    if sig == -1:
        next_m = v
        break

if next_p == 0 and next_m == 0:
    print(0)
    exit()


if next_p*last_p >= next_m*last_m or last_p == 0:

    ans = 1
    skip_flag = False
    for i in range(k):
        v,sig = al_abs[i]
        if not skip_flag and v == last_m and sig == -1:
            ans *= next_p
            skip_flag = True
        else:
            ans *= v
        
        ans %= MOD
    print(ans)
    exit()




elif next_p*last_p <= next_m*last_m:
    ans = 1
    skip_flag = False
    for i in range(k):
        v,sig = al_abs[i]
        if not skip_flag and v == last_p and sig == 1:
            ans *= next_m
            skip_flag = True
        else:
            ans *= v
        ans %= MOD
    print(ans)
    exit()

Solution (Python):
MOD = 10 ** 9 + 7
 
N, K = map(int, input().split())
l = list(map(int, input().split()))
pos = []
neg = []
z = 0
 
for v in l:
    if v > 0:
        pos.append(v)
    elif v < 0:
        neg.append(v)
    else:
        z += 1
pos.sort()
neg.sort()
 
if N - z < K:
    print(0)
elif N - z == K:
    if len(neg) % 2 and z:
        print(0)
    else:
        out = 1
        for v in neg + pos:
            out *= v
            out %= 10 ** 9 + 7
        print(out)
elif len(pos) == 0:
    if K % 2:
        if z:
            print(0)
        else:
            neg.reverse()
            out = 1
            for i in range(K):
                out *= neg[i]
                out %= 10 ** 9 + 7
            print(out)
    else:
        out = 1
        for i in range(K):
            out *= neg[i]
            out %= 10 ** 9 + 7
        print(out)
else:
    out = 1
    neg.reverse()
    if K % 2:
        out = pos.pop()
        K -= 1
    while K:
        if len(pos) >= 2:
            nP = pos[-1] * pos[-2]
        else:
            nP = 0
 
        if len(neg) >= 2:
            nN = neg[-1] * neg[-2]
        else:
            nN = 0
 
        if nP > nN:
            pos.pop()
            pos.pop()
            out *= nP
        else:
            neg.pop()
            neg.pop()
            out *= nN
        out %= MOD
        K -= 2
    print(out)