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):
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if not can_positive: return sorted(P+M, key=lambda x:abs(x))[:k]

    P.sort()
    M.sort(reverse = True)
    p, m = [], []
    while len(p) + len(m) < k:
        if len(P) > 0 and len(M) <= 0: p.append(P.pop())
        elif len(P) <= 0 and len(M) > 0: m.append(M.pop())
        elif P[-1] < -M[-1]: m.append(M.pop())
        else: p.append(P.pop())
    if len(m)%2:
        Mi = M.pop() if len(p)*len(M) else 1  
        Pi = P.pop() if len(m)*len(P) else -1 
        if Mi < 0 and Pi >= 0:
            if abs(p[-1] * Pi) < abs(m[-1] * Mi):
                p.pop()
                m.append(Mi)
            else:
                m.pop()
                p.append(Pi)
        elif Mi < 0:
            p.pop()
            m.append(Mi)
        elif Pi >= 0:
            m.pop()
            p.append(Pi)
    return p + m

n, k = map(int, input().split())
P, M = [], [] 
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if not can_positive: return sorted(P+M, key=lambda x:abs(x))[:k]

    P.sort()
    M.sort(reverse = True)
    debug('k {} n {}'.format(k,n))
    debug('P {}'.format(P))
    debug('M {}'.format(M))
    p, m = [], []
    while len(p) + len(m) < k:
        if len(P) > 0 and len(M) <= 0: p.append(P.pop())
        elif len(P) <= 0 and len(M) > 0: m.append(M.pop())
        elif P[-1] < -M[-1]: m.append(M.pop())
        else: p.append(P.pop())

    debug('p {}'.format(p))
    debug('m {}'.format(m))
    debug('P {}'.format(P))
    debug('M {}'.format(M))

    if len(m)%2:
        Mi = M.pop() if len(p)*len(M) else 1  
        Pi = P.pop() if len(m)*len(P) else -1 
        if Mi < 0 and Pi >= 0:
            if abs(p[-1] * Pi) < abs(m[-1] * Mi):
                p.pop()
                m.append(Mi)
            else:
                m.pop()
                p.append(Pi)
        elif Mi < 0:
            p.pop()
            m.append(Mi)
        elif Pi >= 0:
            m.pop()
            p.append(Pi)
    return p + m

n, k = map(int, input().split())
P, M = [], [] 
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N,K = LI()
A = LI()

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

plus = []
minus = []
zeros = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zeros.append(A[i])

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

if len(plus):
    if K%2:
        ans = plus[0]
        p_place = 1
        m_place = 0
        K -= 1
    else:
        ans = 1
        p_place = 0
        m_place = 0
    while K:
        val1 = plus[p_place]*plus[p_place+1] if p_place <= len(plus)-2 else -float('inf')
        val2 = minus[m_place]*minus[m_place+1] if m_place <= len(minus)-2 else -float('inf')
        if val1 == val2 == -float('inf'):
            if p_place == len(plus)-1:
                ans *= plus[p_place]
                ans %= mod
                K -= 1
            if K:
                print(0)
                exit()
        else:
            K -= 2
            if val1 == -float('inf'):
                ans *= val2
                ans %= mod
                m_place += 2
            elif val2 == -float('inf'):
                ans *= val1
                ans %= mod
                p_place += 2
            elif val1 >= val2:
                ans *= val1
                ans %= mod
                p_place += 2
            else:
                ans *= val2
                ans %= mod
                m_place += 2
    print(ans)
else:
    if K%2:
        if len(zeros):
            print(0)
        else:
            ans = 1
            for i in range(K):
                ans *= -minus[len(minus)-1-i]
                ans %= mod
            print(ans)
    else:
        m_place = 0
        ans = 1
        while K:
            if m_place <= len(minus)-2:
                ans *= minus[m_place]*minus[m_place+1]
                ans %= mod
                m_place += 2
                K -= 2
            else:
                print(0)
                exit()
        print(ans)

Solution (Python):
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

ans=1
if (max(A)<=0 and k%2==1) or n==k:
    for i in range(k):
        ans=ans*A[n-1-i]%mod
else:
    mi=0
    pl=0
    flg=1
    for i in range(k):
        ans=ans*A[i]%mod
        if A[i]>0:
            pl=A[i]
        if A[i]<0:
            mi=A[i]
            flg*=-1
    if ans==0:
        pass
    elif flg==-1:
        mi2=None
        pl2=None
        for i in range(k,n):
            if A[i]>=0:
                pl2=A[i]
                break
        for i in range(k,n):
            if A[i]<=0:
                mi2=A[i]
                break
        can=0
        if mi!=0 and pl2 is not None and pl!=0 and mi2 is not None:
            if pl2*pl > mi2*mi:
                can = pow(mi,-1,mod)*pl2%mod
            else:
                can = pow(pl,-1,mod)*mi2%mod
        elif mi!=0 and pl2 is not None:
            can = pow(mi,-1,mod)*pl2%mod
        elif pl!=0 and mi2 is not None:
            can = pow(pl,-1,mod)*mi2%mod 
        ans=ans*can%mod

print(ans)

Solution (Python):
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

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

def is_ans_plus():
    if len(plus) > 0:
        if n == k:
            if len(minus) % 2 == 0:
                return True
            else:
                return  False
        else:
            return True
    else:
        if k % 2 == 0:
            return True
        else:
            return False

ans = 1
if is_ans_plus():
    if k % 2 == 1:
        ans *= plus.pop()
        k -= 1
    for i in range(k // 2):
        plus_pair, minus_pair = -1, -1
        if len(plus) >= 2:
            plus_pair = plus[-1] * plus[-2]
        if len(minus) >= 2:
            minus_pair = minus[-1] * minus[-2]
        if plus_pair >= minus_pair:
            ans *= plus_pair
            plus.pop()
            plus.pop()
        else:
            ans *= minus_pair
            minus.pop()
            minus.pop()
        ans %= mod
else:
    ans = -1
    A = sorted([abs(a) for a in A])
    for i in range(k):
        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()))

A.sort(reverse = True)
ans = 1
if A[-1] >= 0:
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif A[0] < 0:
    if K % 2 == 0:
        for i in range(K):
            ans *= A[N-1-i]
            ans %= MOD
    else:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
else:
    r,l = N-1,0
    n = 0
    while n < K:
        if K-n == 1:
            ans *= A[l]
            ans %= MOD
            n += 1
        else:
            if A[r]*A[r-1] > A[l]*A[l+1]:
                ans *= (A[r]*A[r-1])
                ans %= MOD
                r -= 2
                n += 2
            else:
                ans *= A[l]
                ans %= MOD
                l += 1
                n += 1
print(ans)

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

A.sort(reverse = True)
ans = 1
if A[-1] >= 0:
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif A[0] < 0:
    if K % 2 == 0:
        for i in range(K):
            ans *= A[N-1-i]
            ans %= MOD
    else:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
else:
    r,l = N-1,0
    n = 0
    while n < K:
        if K-n == 1:
            ans *= A[l]
            ans %= MOD
            n += 1
        else:
            if A[r]*A[r-1] > A[l]*A[l+1]:
                ans *= (A[r]*A[r-1])
                ans %= MOD
                r -= 2
                n += 2
            else:
                ans *= A[l]
                ans %= MOD
                l += 1
                n += 1
print(ans)

Solution (Python):
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        P.sort()
        M.sort(reverse=True)
        a = [P.pop()] if k%2 else [1]
        while len(P) >= 2: a.append(P.pop() * P.pop())
        while len(M) >= 2: a.append(M.pop() * M.pop())
        return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]
    else: return sorted(P+M, key=lambda x:abs(x))[:k]

n, k = map(int, input().split())
P, M = [], []
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        P.sort()
        M.sort(reverse = True)
        a = [P.pop()] if k%2 else [1]
        while len(P) >= 2: a.append(P.pop() * P.pop())
        while len(M) >= 2: a.append(M.pop() * M.pop())
        return a[:k%2] + sorted(a[1:], reverse = True)[:(k-k%2)//2]
    else: return sorted(P+M, key=lambda x: abs(x))[:k]

n, k = map(int, input().split())
P, M = [], [] 
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

def solve():
    debug('k {} n {}'.format(k,n))
    debug('P {}'.format(P))
    debug('M {}'.format(M))
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        debug('positive')
        P.sort()
        M.sort(reverse = True)
        p0 = []
        if k%2: p0.append(P.pop())
        ar = []
        while len(P) >= 2: ar.append(P.pop() * P.pop())
        while len(M) >= 2: ar.append(M.pop() * M.pop())
        ar.sort(reverse = True)
        debug('p0 {}'.format(p0))
        debug('ar {}'.format(ar))
        debug('ar[:k] {}'.format(ar[:(k-k%2)//2]))
        return p0 + ar[:(k-k%2)//2]
    else: 
        debug('negative')
        return sorted(P+M, key=lambda x: abs(x))[:k]


n, k = map(int, input().split())
P, M = [], [] 
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

def solve():
    P.sort(reverse = True)
    M.sort()
    debug('k {} n {}'.format(k,n))
    debug('P {}'.format(P))
    debug('M {}'.format(M))
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        debug('positive')
        P.sort()
        M.sort(reverse = True)
        p0 = []
        if k%2: p0.append(P.pop())
        ar = []
        while len(P) >= 2: ar.append(P.pop() * P.pop())
        while len(M) >= 2: ar.append(M.pop() * M.pop())
        ar.sort(reverse = True)
        debug('p0 {}'.format(p0))
        debug('ar {}'.format(ar))
        debug('ar[:k] {}'.format(ar[:(k-k%2)//2]))
        return p0 + ar[:(k-k%2)//2]
    else: 
        debug('negative')
        return sorted(P+M, key=lambda x: abs(x))[:k]


n, k = map(int, input().split())
P, M = [], [] 
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
import numpy as np
 
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7
 
def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans
 
def solve():
    
    if N == K:
        return prod(A)
 
    
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])
 
    
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))
 
    ans = 1
    if K % 2 == 1: 
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    
    if len(posA) % 2 == 1: 
        posA = posA[1:]
    if len(negA) % 2 == 1: 
        negA = negA[:-1]
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0).tolist()
    pairs = sorted(pairs, reverse=True)[:K//2]
    ans = ans * prod(pairs) % M
 
    return ans
 
print(solve())

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
use = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            use.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            use.append(a[i])
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans % mod)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans *= max(a[k:])
            print(ans % mod)
            quit()
        if plus:
            ans = -ans
            ans *= pow(plus[-1], mod-2, mod)
            ans %= mod
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans1 = plus[-1] * max(a[k:])
            ans2 = minus[-1] * min(a[k:])
            print(max(ans1, ans2) * ans % mod)
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans *= max(a[k:])
            print(ans % mod)
else:
    print(ans)

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
p, q = [], []
for x in a:
    if x >= 0: p.append(x)
    else: q.append(x)
lp, lq = len(p), len(q)

def sp():
    p.sort(reverse=True)
    q.sort()
    ans = p[0] if k % 2 else 1
    s = []
    for i in range(0, lq-1, 2):
        s.append(q[i]*q[i+1])
    for i in range(k % 2, lp-1, 2):
        s.append(p[i]*p[i+1])
    s.sort(reverse=True)
    for i in range(k//2):
        ans *= s[i]
        ans %= MOD
    print(ans)

def sq():
    a.sort(key=lambda x: abs(x))
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= MOD
    print(ans)

if k % 2 and not p: sq()
elif n == k and lq % 2: sq()
else: sp()

Solution (Python):
from collections import deque 
N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9+7
ans = 1
sign = 1
if K%2 == 1: 
    if len(pos) > 0:
        ans = ans*pos.pop() % mod
    else:
        ans = ans*neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0: 
    if len(pos) == 1 and len(neg) == 1:
        ans = ans*-neg.pop()*pos.pop() % mod
    elif sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.pop()*neg.pop() % mod
        else:
            ans = ans*pos.pop()*pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.popleft()*neg.popleft() % mod
        else:
            ans = ans*pos.popleft()*pos.popleft() % mod
    K -= 2
ans = ans*sign % mod
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline


def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    

def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp


def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);


def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 


def upper_bound(a, x, lo=0, hi = None):
    if hi == None:
        hi = len(a);
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo


def primefs(n):
    
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    
    
    return primes


def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 


def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b









def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;




def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x


def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime


MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    




def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    
    


def int_array():
    return list(map(int, input().strip().split()))

def str_array():
    return input().strip().split();


MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');



n, k = int_array(); a = int_array();
pos = []; neg = []; ans = 1;
for i in a:
    if i < 0:
        neg.append(i);
    else:
        pos.append(i);

if n == k:
    for i in a:
        ans = (ans * i) % MOD;
elif not pos:
    if k & 1:
        neg.sort(reverse = 1);
    else:
        neg.sort();
    for i in range(k):
        ans = (ans * neg[i]) % MOD;
else:
    pos.sort(); neg.sort(reverse = 1);
    if k & 1:
        ans = pos.pop();
    for _ in range(k // 2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] >= neg[-1] * neg[-2]:
                ans = (ans * pos.pop()) % MOD;
                ans = (ans * pos.pop()) % MOD;
            else:
                ans = (ans * neg.pop()) % MOD;
                ans = (ans * neg.pop()) % MOD;
        elif len(pos) > 1:
            ans = (ans * pos.pop()) % MOD;
            ans = (ans * pos.pop()) % MOD;
        else:
            ans = (ans * neg.pop()) % MOD;
            ans = (ans * neg.pop()) % MOD;
print(ans);

Solution (Python):



def resolve():
    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)
        return

    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)
    return
resolve()

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

a = list(map(int, input().split()))
a_pos = sorted([i for i in a if i >= 0])
a_neg = sorted([i for i in a if i < 0], reverse=True)

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
        ans *= a_pos.pop()
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    ans %= mod

print(ans)

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

a = list(map(int, input().split()))
a_pos = sorted([i for i in a if i >= 0])
a_neg = sorted([i for i in a if i < 0], reverse=True)

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
        ans *= a_pos.pop()
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    ans %= mod

else:
    print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007
plus = []
minus = []
ans = 1
lp = 0
lm = 0
lz = 0
for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
    lp += 1
  elif A[k] < 0:
    minus.append(A[k])
    lm += 1
  else:
    lz += 1
plus.sort(reverse = True)
minus.sort()
def main(mp, mm, plus, minus):
  mod = 1000000007
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * minus[k] % mod
  print(ans)
  exit()
if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * minus[- k - 1] % mod
      print(ans)
      exit()
  else:
    main(0, K, plus, minus)
elif lm == 0:
  main(K, 0, plus, minus)
p = 0
m = 0
for _ in range(K):
  if plus[p] >= -1 * minus[m]:
    p += 1
    if p == lp:
      m = K - p
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break
if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)

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

mod = 10 ** 9 + 7
plus = []
lz = 0
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(A[k])
  else:
    lz += 1
plus.sort(reverse = True)
minus.sort()
lp = len(plus)
lm = len(minus)

def main(mp, mm, plus, minus):
  mod = 10 ** 9 + 7
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * minus[- k - 1] % mod
      print(ans)
      exit()
  else:
    main(0, K, plus, minus)
elif lm == 0:
  main(K, 0, plus, minus)

p = 0
m = 0
for _ in range(K):
  if plus[p] >= -1 * minus[m]:
    p += 1
    if p == lp:
      m = K - p
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)

Solution (Python):






def inverse(a, p):
    """逆元"""
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


def dev_mod(a, b, mod):
    """a(= A % mod) / b を mod で割った余り"""
    return (a * inverse(b, mod)) % mod






def solve(N, K, As):
    mod = 10 ** 9 + 7
    As.sort()
    ans = 1
    if N == K:
        for a in As:
            ans = (ans * a) % mod
    elif As[-1] < 0 and K % 2 == 1:
        for k in range(1, K + 1):
            ans = (ans * As[- k]) % mod
    else:
        As.sort(key=abs)
        last_p = -1
        last_m = -1
        cnt_m = 0
        for k in range(1, K + 1):
            ans = (ans *  As[- k]) % mod
            if As[- k] < 0:
                last_m = As[- k]
                cnt_m += 1
            else:
                last_p = As[- k]
        if cnt_m % 2 == 1:
            mlt_p = max(As[:N - K])
            mlt_m = min(As[:N - K])
            if last_p < 0:
                ans = dev_mod(ans, last_m, mod) * mlt_p % mod
            elif mlt_m >= 0:
                ans = dev_mod(ans, last_m, mod) * mlt_p % mod
            elif mlt_p < 0:
                ans = dev_mod(ans, last_p, mod) * mlt_m % mod
            else:
                if abs(last_p * mlt_p) <= abs(last_m * mlt_m):
                    ans = dev_mod(ans, last_p, mod) * mlt_m % mod
                else:
                    ans = dev_mod(ans, last_m, mod) * mlt_p % mod
    print(ans % mod)































if __name__ == '__main__':
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    
    
    
    solve(N, K, As)

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)
lz = len(zero)

if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus):
  mod = 10 ** 9 + 7
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)