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

Solution (Python):

import sys
import heapq

MOD = 1000000007  

def containPositive(arr):
    for a in arr:
        if a >= 0:
            return True
    return False

def solve(N: int, K: int, A: "List[int]"):
    if N == K:
        m = 1
        for a in A:
            m = m*a%MOD
        print(m)
    elif not containPositive(A):
        A = list(reversed(sorted(A))) if K%2 == 1 else list(sorted(A))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else:
        m = 1
        B = [(abs(a),a) for a in A]
        B = list(reversed(sorted(B)))
        lastNegative = 0
        lastPositive = 1
        hadPositive = False
        for i in range(K):
            a = B[i][1]
            if a < 0:
                if lastNegative == 0:
                    lastNegative = a
                else:
                    m = m*lastNegative*a%MOD
                    lastNegative = 0
            else:
                if a > 0 and lastPositive != 1:
                    m = m*lastPositive%MOD
                if a > 0:
                    lastPositive = a
                    hadPositive = True
                else:
                    m=m*a%MOD
        if lastNegative == 0:
            print(m*lastPositive%MOD)
        else:
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            if nextNegative == 0:
                m = m*B[K][1]
                print(m*lastPositive%MOD)
            else:
                c1 = lastNegative*nextNegative
                nextPositive = 0
                k = K
                while k < N:
                    a = B[k][1]
                    if a >=0:
                        nextPositive = a
                        break
                    k+=1
                c2 = nextPositive*lastPositive
                if not hadPositive:
                    m = m*nextPositive%MOD
                    
                    
                    
                    
                    
                    print(m)
                    exit()
                if c1 > c2 or not hadPositive:
                    m = m*lastNegative*nextNegative%MOD
                    
                    
                    
                    
                    
                    print(m)
                else:
                    
                    
                    
                    
                    
                    m =m*nextPositive*lastPositive%MOD
                    print(m)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, K, A)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * ba % mod
        if bb < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:][::-1]:
        if bb < 0:
            nb = ba
        else:
            pb = ba
    if pa == -1 or nb == -1:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print(p * nb * pow(pa, mod - 2, mod) % mod)
    elif pa * pb > na * nb:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    else:
        print(p * nb * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    plus = []
    minus = []
    for a in A:
        if a >= 0:
            heapq.heappush(plus, -a)
        else:
            heapq.heappush(minus, a)

    ans = 1

    
    if len(plus) < K - min((K - K % 2), (len(minus) - len(minus) % 2)):
        plus = []
        minus = []
        for a in A:
            if a >= 0:
                heapq.heappush(plus, a)
            else:
                heapq.heappush(minus, -a)

        while K > 0:
            if plus:
                x = plus[0]
            else:
                x = float("inf")

            if minus:
                y = -minus[0]
            else:
                y = float("inf")

            if abs(x) <= abs(y):
                ans *= x
                if plus:
                    heapq.heappop(plus)
            else:
                ans *= y
                if minus:
                    heapq.heappop(minus)

            ans %= MOD
            K -= 1

        print(ans)

    else:
        while K > 0:
            if K >= 2 and len(minus) >= 2 and len(plus) >= 2:
                x1 = plus[0]
                x2 = plus[1]
                y1 = minus[0]
                y2 = minus[1]
                if x1 * x2 <= y1 * y2:
                    y1 = heapq.heappop(minus)
                    y2 = heapq.heappop(minus)
                    ans *= (y1 * y2)
                    ans %= MOD
                    K -= 2
                else:
                    x1 = -heapq.heappop(plus)
                    ans *= x1
                    ans %= MOD
                    K -= 1
            elif K >= 2 and len(minus) >= 2:
                y1 = heapq.heappop(minus)
                y2 = heapq.heappop(minus)
                ans *= (y1 * y2)
                ans %= MOD
                K -= 2
            else:
                x = -heapq.heappop(plus)
                ans *= x
                ans %= MOD
                K -= 1

        print(ans % MOD)


if __name__ == '__main__':
    main()

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


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = modint(1)
    if N == K:
        for a in A:
            ans *= a
        return print(ans)
    elif all(a < 0 for a in A) and K % 2 == 1:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
        return print(ans)
    
    A.sort(reverse=True, key=abs)
    if sum(a < 0 for a in A[:K]) % 2 == 0:
        for a in A[:K]:
            ans *= a
    else:
        ans1 = modint(1)  
        ans2 = modint(1)  
        p_remove = False
        x1 = INF
        for a in A[:K][::-1]:
            if a > 0 and not p_remove:
                p_remove = True
                x1 = a
                continue
            ans1 *= a
        n_remove = False
        x2 = INF
        for a in A[:K][::-1]:
            if a < 0 and not n_remove:
                n_remove = True
                x2 = a
                continue
            ans2 *= a
        y1 = 0  
        y2 = 0  
        for a in A[K:]:
            if y1 == 0 and a < 0:
                y1 = a
            if y2 == 0 and a > 0:
                y2 = a
            if y1 != 0 and y2 != 0:
                break
        ans1 *= y1
        ans2 *= y2
        if x1 != INF and x2 != INF:
            if abs(x2*y1) <= abs(x1*y2):
                ans = ans2
            else:
                ans = ans1
        elif x1 == INF and x2 == INF:
            
            ans = 0
        elif x1 == INF:
            
            ans = ans2
        else:
            
            
            
            ans = ans1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def e_multiplication_4(MOD=10**9 + 7):
    from functools import reduce
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    sign = {-1: 0, 0: 0, 1: 0}  
    for a in A:
        if a == 0:
            sign[0] += 1
            continue
        sign[a // abs(a)] += 1

    if sign[1] == 0 and K % 2 == 1:
        
        A.sort(reverse=True)
        return reduce(lambda x, y: (x * y) % MOD, A[:K])
    if sign[1] == 0 and K % 2 == 0:
        
        A.sort()
        return reduce(lambda x, y: (x * y) % MOD, A[:K])

    A.sort()
    ans = 1
    i, j = 0, N - 1
    while K > 0:
        
        
        
        if K > 1 and A[i] * A[i + 1] >= A[j] * A[j - 1]:
            ans *= A[i] * A[i + 1]
            i += 2
            K -= 2
        else:
            ans *= A[j]
            j -= 1
            K -= 1
        ans %= MOD
    return ans

print(e_multiplication_4())

Solution (Python):
from heapq import heappush, heappop


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

MOD = 10**9 + 7


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

elif max(A) < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    

    
    

    if K%2 == 1:
        ans = A.pop(0)  
        n = (K-1)//2
    else:
        ans = 1
        n = K//2

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

    
    cand = []  

    BIGINT = 10**9 + 1  
    tmp1 = BIGINT
    tmp2 = BIGINT

    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = a
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

    
    for i in range(n):
        ans *= -heappop(cand)
        ans %= MOD
    print(ans)

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
    exit()

while k > 0:
    if k == 1 or len(mia) <= 1:
        if len(pla) == 0:
            cnt *= mia.pop()
        elif len(pla) > 0:
            cnt *= pla.pop()
        k -= 1
    elif len(pla) <= 1:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    elif pla[-1] * pla[-2] > mia[-1] * mia[-2]:
        cnt *= pla.pop()
        k -= 1
    elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    cnt %= mod
else:
    print(cnt)

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt *= mia.pop()
            elif len(pla) > 0:
                cnt *= pla.pop()
            k -= 1
        elif len(pla) <= 1:
            cnt *= mia.pop() * mia.pop()
            k -= 2
        elif pla[-1] * pla[-2] > mia[-1] * mia[-2]:
            cnt *= pla.pop()
            k -= 1
        elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
            cnt *= mia.pop() * mia.pop()
            k -= 2
        cnt %= mod
print(cnt)

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt *= mia.pop()
            elif len(pla) > 0:
                cnt *= pla.pop()
            k -= 1
        elif len(pla) <= 1:
            cnt *= mia.pop() * mia.pop()
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt *= pla.pop()
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt *= mia.pop() * mia.pop()
                k -= 2
        cnt %= mod
print(cnt)

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt *= mia.pop()
            elif len(pla) > 0:
                cnt *= pla.pop()
            k -= 1
        elif len(pla) <= 1:
            cnt *= mia.pop() * mia.pop()
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt *= pla.pop()
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt *= mia.pop() * mia.pop()
                k -= 2
        cnt %= mod
print(cnt)

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop()
            elif len(pla) > 0:
                cnt = cnt * pla.pop()
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() * mia.pop()
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop()
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop()
                k -= 2
        cnt %= mod
print(cnt)

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
print(cnt)

Solution (Python):

    
    
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            if k == 1:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif k > 1:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
print(cnt)

Solution (Python):
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max*positive_big_min > negative_small_min*negative_big_max:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Solution (Python):
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort(reverse = True)
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if K == 1:
          ans = A_p[0]
        elif posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          if posi_p != 0:
            ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
            ans = ans*A_m[posi_m]%MOD
          else:
            ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
            ans = ans *A_p[posi_p]%MOD
            
    print(ans%MOD)
          
    
if __name__ == "__main__":
  main()

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):
n,k,*a=map(int,open(0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
i=0
while k>1:
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:i+=2
 else:x=p()*p()
 s=s*x%(10**9+7);k-=2
print(s)

Solution (Python):
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
while k>1:
 if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:i+=2
 else:x=p()*p()
 s=s*x%(10**9+7);k-=2
print(s)

Solution (Python):





























mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

if n==k:
    print(multarray(a))
    exit()

ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])

ap.sort(reverse=True)
am.sort()

if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)



p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])



if k%2==0:
    print(multarray(ans))
    exit()
if p==len(ap):
    
    check_i=ans.index(ap[p-1]*ap[p-2])
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    print(multarray(ans))
else:
    
    
    
    ans_cand=[]
    
    ans_cand.append(multarray(ans)*ap[p]%mod)
    if p>=2:
        
        check_i=ans.index(ap[p-1]*ap[p-2])
        
        ans[check_i]=ap[p-2]
        ans.append(apm2[k//2][0])
        ans_cand.append(multarray(ans))
    print(max(ans_cand))

Solution (Python):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
from collections import deque

a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)


plus_flg = False
tmp = plus - k
if tmp >= 0:
    plus_flg = True
elif (-tmp <= minus and -tmp%2 == 0) or (-tmp < minus and plus >= 1):
    plus_flg = True


if plus_flg:
    ans = 1
    cnt = 0

    while cnt < k:
        if k - cnt >= 2:
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
                cnt += 2
            else:
                ans *= que.pop()
                ans %= mod
                cnt += 1
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)




elif zero > 0:
    print(0)


else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)

Solution (Python):
import numpy as np

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = int(1e9+7)
    p = []
    m = []
    for a in A:
        if a >= 0:
            p.append(a)
        else:
            m.append(a)
    p.sort(reverse=True)
    m.sort(reverse=False)
    ans = 1
    if sum(np.sign(A)) == -N and K%2 == 1:
        A = sorted(A, reverse=True)
        for i in range(K):
            ans = (ans*A[i])%mod
        print(ans)
        return
    if N == K:
        for i in range(K):
            ans = (ans*A[i])%mod
        print(ans)
        return

    m_pair = []
    p_pair = []
    if K%2 == 1:
        ans *= p.pop(0)%mod
    for i in range(0, len(m), 2):
        if i+1 < len(m):
            m_pair.append(m[i]*m[i+1])
        
        
    for i in range(0, len(p), 2):
        if i+1 < len(p):
            p_pair.append(p[i]*p[i+1])
        else:
            p_pair.append(p[i])
    pairs = m_pair[:]
    pairs.extend(p_pair)
    pairs.sort(reverse=True)
    for i in range(K//2):
        ans = (ans*pairs[i])%mod
    print(ans)

main()

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

plus = []
minus = []
for i in a:
    if i >= 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
i, j = 0, 0
if n == k:
    for x in a:
        ans = (ans * x) % mod
else:
    if k % 2 == 1:
        if len(plus) != 0:
            ans = plus[0]
            i += 1
        else:
            minus.sort()
            ans = -minus[0]
            j += 1
    while i + j != k:
        x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
        x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
        if x_p >= x_m and i != len(plus):
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

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

plus = []
minus = []
for i in a:
    if i >= 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
i, j = 0, 0
if n == k:
    if len(plus) % 2 == 1:
        ans *= plus[0]
        i += 1
    if len(minus) % 2 == 1:
        ans *= -minus[0]
        j += 1
if n != k and k % 2 == 1:
    if len(plus) != 0:
        ans = plus[0]
        i += 1
    else:
        minus.sort()
        ans = -minus[0]
        j += 1
while i + j != k:
    x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
    x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
    if x_p >= x_m and i != len(plus):
        ans = (ans * x_p) % mod
        i += 2
    else:
        ans = (ans * x_m) % mod
        j += 2
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    M, P = [], []
    for a in A:
        M.append(a) if a < 0 else P.append(a)

    m, p = len(M), len(P)
    ok = False
    if p > 0:
        ok = m % 2 == 0 if n == k else True
    else:
        ok = k % 2 == 0

    res = 1
    if not ok:
        A.sort(key=lambda x: abs(x))
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort()
        M.sort(reverse=True)
        if k % 2:
            a = P.pop()
            res = (res * a) % mod
        M_2 = []
        while len(P) >= 2:
            a = P.pop()
            a *= P.pop()
            M_2.append(a)
        while len(M) >= 2:
            a = M.pop()
            a *= M.pop()
            M_2.append(a)
        M_2.sort(reverse=True)
        for i in range(k // 2):
            res = (res * M_2[i]) % mod
    print(res)


if __name__ == '__main__':
    resolve()