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 copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
"""
N, K = LI()
A = LI()

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

tmps = []
A_abs = abssort(A)
cnt = 0
while len(tmps) > K:

    if A_abs[cnt] != 0:
        tmps.append(A_abs[i])
        cnt += 1

cnt = 0
for i in range(K):
    if tmps[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    ans = 1
    for i in range(K):
        ans *= tmps[i]
        ans = ans % mod
    print(ans)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmps)
    tmp_2 = copy.deepcopy(tmps)
    tmp_1.reverse()
    tmp_2.reverse()
    tmp_2_ = 0
    tmp_1_ = 0
    
    for i in range(K):
        if tmp_1[i] < 0:
            tmp_1.remove(tmp_1[i])
            break
    
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1.append(A_abs[i])
            tmp_1_ = 1
            break
    else:
        
        tmp_1 = []
        tmp_1_ = -1 
        A_abs.reverse()
        for i in range(K):
            tmp_1.append(A_abs[i])

    
    cnt = 0
    for i in range(K):
        if tmp_2[i] > 0:
            tmp_2.remove(tmp_2[i])
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2.append(A_abs[i])
                tmp_2_ = 1
                break
        else:
            tmp_2_ = 0
    else:
        tmp_2_ = -1




tmp_1_m = 1
tmp_2_m = 1
for i in range(K):
    tmp_1_m *= tmp_1[i]
    tmp_1_m = tmp_1_m % mod

if tmp_2_ == 0:
    pass
else:
    for i in range(K):
        tmp_2_m *= tmp_2[i]
        tmp_2_m = tmp_2_m % mod


if tmp_2_ == 0:
    print(tmp_1_m)
elif tmp_1_ == 1 and tmp_2_ == -1:
    print(tmp_1_m)
elif tmp_1_ == -1 and tmp_2_ == 1:
    print(tmp_2_m)
elif tmp_1_ == 1 and tmp_2_ == 1:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif abs(tmp_1[i]) > abs(tmp_2[i]):
            print(tmp_2_m)
            sys.exit()
        else:
            print(tmp_1_m)
            sys.exit()
else:
    print(tmp_1_m)
    
    
    
    
    
    
    
    
    
    """

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


A_abs = sorted(A, key = lambda x:abs(x))
A_p = [] 
A_n = [] 
for i in range(N):
    if A[i] < 0:
        A_n.append(A[i])
    else:
        A_p.append(A[i])

A_n.sort()
A_p.sort(reverse = True)

ok = True
if len(A_p) > 0:
    
    if N == K:
        
        ok = (len(A_n) % 2 == 0)
        
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if ok == False:
    for i in range(K):
        ans *= A_abs[i]
        ans = ans % mod
else:
    if K % 2 == 1:
        
        ans *= A_p[0]
        ans = ans % mod
        A_p = A_p[1:]
    position = 0
    pairs = []
    cnt_p = len(A_p)
    cnt_n = len(A_n)
    while cnt_p - position > 1:
        pairs.append(A_p[position] * A_p[position + 1])
        position += 2
    position = 0
    while cnt_n - position > 1:
        pairs.append(A_n[position] * A_n[position + 1])
        position += 2

    pairs.sort(reverse=True)
    for i in range(K // 2):
        ans *= pairs[i]
        ans = ans % mod

print(ans)

Solution (Python):
_MULTITEST = False

def solve():
    MOD = int(1e9) + 7

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

    neg = sum(1 for x in a if x < 0)
    pos = sum(1 for x in a if x > 0)
    zero = a.count(0)
    
    
    ans_is_neg = False
    if n == k:
        if zero == 0 and neg % 2 == 1:
            ans_is_neg = True
    else:
        if pos == 0:
            if zero == 0:
                if k % 2 == 1:
                    ans_is_neg = True
    
    
    

    
    if ans_is_neg:
        prod = 1
        for i in a[n-k:n]:
            prod = (prod * i) % MOD
        print(prod)
    else:
        prod = 1
        p1 = 0; p2 = n-1;
        while k > 0:
            if k > 1 and p1 + 1 < n and 0 < p2 and a[p1] * a[p1+1] > a[p2] * a[p2-1]:
                prod = (prod * a[p1] * a[p1 + 1]) % MOD
                p1 += 2; k -= 2;
            else:
                prod = (prod * a[p2]) % MOD
                p2 -= 1; k -= 1;
        print(prod)


if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
mod = 10**9+7
if (max(a) < 0 and k%2) or n == k:
  ans = 1
  for i in range(n-k,n):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
cntn = 0
cntp = n-1
if k%2:
  ans = a[-1]
  cntp -= 1
  n -= 1
else:
  ans = 1
for i in range(k//2):
  tmp = 0
  if (cntn < n-1 and a[cntn+1] < 0) and (cntp > 0 and a[cntp-1] >= 0):
    if a[cntn]*a[cntn+1] > a[cntp-1]*a[cntp]:
      tmp = a[cntn]*a[cntn+1]
      cntn += 2
    else:
      tmp = a[cntp-1]*a[cntp]
      cntp -= 2
  elif cntn < n-1 and a[cntn+1] < 0:
    tmp = a[cntn]*a[cntn+1]
    cntn += 2
  else:
    tmp = a[cntp-1]*a[cntp]
    cntp -= 2  
  ans *= tmp
  ans %= mod
print(ans)

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(-i)
    else:
        zero += 1

plus.sort()
minus.sort()
p_l = len(plus)
m_l = len(minus)
cnt = 0


def tail_num(p):
    return p[-1] * p[-2]


if k == 1:
    print(max(a) % num)
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    if m_l % 2 == 0:
        print(ans)
    else:
        print(-ans % num)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        if 0 in a:
            print(0)
        else:
            for j in range(k):
                ans = ans * (minus[j]) % num
            print(-ans % num)
else:
    if k % 2 == 1:
        ans = ans * plus.pop() % num
        p_l -= 1
    for i in range(k//2):
        if p_l >= 2 and m_l >= 2:
            if tail_num(minus) >= tail_num(plus):
                ans = ans * tail_num(minus) % num
                minus.pop()
                minus.pop()
                m_l -= 2
            else:
                ans = ans * tail_num(plus) % num
                plus.pop()
                plus.pop()
                p_l -= 2
        else:
            if p_l <= 1:
                ans = ans * tail_num(minus) % num
                minus.pop()
                minus.pop()
                m_l -= 2
            else:
                ans = ans * tail_num(plus) % num
                plus.pop()
                plus.pop()
                p_l -= 2
    print(ans)

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

p = []
m = []
for i in a:
    if i >= 0:p.append(i)
    elif i < 0:m.append(i)

p.sort(reverse=True)
m.sort()
res = 1
if n == k:
    for i in a:
        res = (res * i) %mod
    print(res)
    exit()
    
if len(p) == 0 and k % 2 == 1:
    for i in range(k):
        res = (res * m[-(i + 1)]) %mod
    print(res)

else:
    p_ind = 0
    m_ind = 0
    while k:
        if k == 1:
            res = (res * p[p_ind]) % mod
            break
        
        temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else 0
        temp1 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else 0
        if temp > temp1:
            res = (res * p[p_ind]) %mod
            p_ind += 1
            k -= 1
        else:
            res = (res * temp1) %mod
            m_ind += 2
            k -= 2
    print(res)

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

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

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

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

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
T = {"mi":0, "pu":0, "zero":0}

for i in range(N):
    if A[i] < 0:
        T["mi"] += 1
    elif A[i] == 0:
        T["zero"] += 1
    else:
        T["pu"] += 1
mod = 10**9+7
for i in range(N):
    if A[i] < 0:
        B.append([A[i]*(-1), 1])
    else:
        B.append([A[i], 0])
A.sort()
B.sort(reverse=True)

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

if c % 2 == 0:
    print(ans)
elif K > T["pu"]+T["mi"]:
    print(0)
elif T["mi"] == 1 and K > T["pu"]:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif T["pu"] == 1 and K > T["mi"]:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif T["pu"] == 0:
    ans = 1
    A.reverse()
    for i in range(K):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
else:
    change1 = B[K-1][1]
    change2 = (change1 + 1)%2
    chindex1 = K-1
    chindex2 = -1
    for i in range(K-1, -1, -1):
        if B[i][1] == change2:
            chindex2 = i
            break
    afterindex1 = -1
    afterindex2 = -1
    for i in range(K, N):
        if B[i][1] == change2:
            afterindex1 = i
            break
    for i in range(K, N):
        if B[i][1] == change1:
            afterindex2 = i
            break
    result1 = 0
    result2 = 0
    if chindex1 >= 0 and afterindex1 >= 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex1:
                if i != chindex1:
                    ans *= B[i][0]
                    ans %= mod
        result1 = ans
    if chindex2 >= 0 and afterindex2 >= 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex2:
                if i != chindex2:
                    ans *= B[i][0]
                    ans %= mod
        result2 = ans
    if result1 == 0 and result2 == 0:
        print(0)
    elif result1 == 0:
        print(result2)
    elif result2 == 0:
        print(result1)
    elif B[afterindex1][0]*B[chindex2][0] - B[afterindex2][0]*B[chindex1][0] > 0:
        print(result1)
    else:
        print(result2)

Solution (Python):
def main():
    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


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    p = 0
    m = 0
    for i in a:
        if i >= 0:
            p += 1
        else:
            m += 1
    f = 1
    for x in range(min(p,k)+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = []
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ans = 1
    if k&1:
        m = max(a)
        for i in range(n):
            if a[i] == m:
                break
        a = a[:i]+a[i+1:]
        ans *= m
        k -= 1
    for i in a:
        if i < 0:
            k1 ^= 1
            s *= -i
            if not k1:
                minus.append(s)
                s = 1
        else:
            k2 ^= 1
            s2 *= i
            if not k2:
                minus.append(s2)
                s2 = 1
    x = k>>1
    minus.sort(reverse = True)
    for m in minus[:x]:
        ans *= m
        ans %= mod
    print(ans%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        if max(a) <= 0:
            ans = 1
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
            print(ans)
        else:
            A = min(a[k:])
            B = max(a[k:])
            if A >= 0:
                ans *= pow(L, mod - 2, mod)
                ans *= B
            else:
                if A * L > B * R:
                    ans *= pow(R, mod - 2, mod)
                    ans *= A
                else:
                    ans *= pow(L, mod - 2, mod)
                    ans *= B
            print(ans % mod)
    else:
        print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np
n, k = map(int, input().split())
aa = list(map(np.int64, input().split()))
aa = np.array(aa)

def mul(dd):
    mod = 10**9+7
    ret = 1
    for d in dd:
        ret = (ret*d)%mod
    return ret

def sol(aa, n, k):
    mod = 10**9+7
    aap = aa[aa>0]
    aam = aa[aa<0]
    if n == k:
        return mul(aa)
    if len(aap) + 2*(len(aam)//2) < k:
        return 0

    
    if len(aam) == n:
        aam.sort()
        if k%2==1:
            return mul(aam[-k:])
        else:
            return mul(aam[:k])

    aap = aa[aa>=0]
    aap.sort()
    aap = aap[::-1]
    aam.sort()

    ret=1
    if k%2 >0:
        k = k-1
        ret *= aap[0]
        aap = aap[1:]

    aap2 = [aap[2*i]*aap[2*i+1] for i in range(len(aap)//2)]
    aam2 = [aam[2*i]*aam[2*i+1] for i in range(len(aam)//2)]
    aap2.extend(aam2)
    aap2.sort(reverse=True)
    aap2 = [i%mod for i in aap2]
    return (ret*mul(aap2[:k//2]))%mod
print(sol(aa, n, k))

Solution (Python):
N,K = map(int,input().split())
la = list(map(int,input().split()))
la = sorted(la)
la = sorted(la,key=abs,reverse=True)
lg = la[:K]
lgp = []
lgm = []
lr = la[K:]
lrp = []
lrm = []
for a in lg:
    if a >= 0:
        lgp.append(a)
    else:
        lgm.append(a)
for a in lr:
    if a >= 0:
        lrp.append(a)
    else:
        lrm.append(a)
if len(lgm) % 2 == 1:
    if len(lrp) > 0 and len(lrm) > 0:
        if len(lgp) > 0 and len(lgm) > 0:
            if lgp[len(lgp) - 1] * lrp[0] > lgm[len(lgm) - 1] * lrm[0]:
                lg.pop(lg.index(lgm[len(lgm) - 1]))
                lg.append(lrp[0])
            else:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
        else:
            if len(lgp) > 0:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg.pop(lg.index(lgm[len(lgm) - 1]))
                lg.append(lrp[0])
    elif len(lrp) > 0:
        if len(lgm) > 0:
            lg.pop(lg.index(lgm[len(lgm) - 1]))
            lg.append(lrp[0])
        else:
            lg = la[N - K:]
    elif len(lrm) > 0:
        if len(lgp) > 0:
            lg.pop(lg.index(lgp[len(lgp) - 1]))
            lg.append(lrm[0])
        else:
            lg = la[N - K:]
ans = 1
for a in lg:
    ans *= a
    ans %= 10 ** 9 + 7
print(ans)

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




def modinv(a):
  b = MOD
  u = 1
  v = 0
  while b != 0:
    t = a // b
    a -= t * b
    a, b = b, a
    u -= t * v
    u, v = v, u
  u %= MOD
  if u < 0:
    u += MOD
  return u


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







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

b = a[:k]
c = a[k:]

n = 0
pro_abs_b = 1
for e in b:
  if e < 0:
    n += 1
  pro_abs_b *= abs(e)
  pro_abs_b %= MOD
pro_b = (-1)**n * pro_abs_b % MOD

n_ = 0
pro_abs_ = 1
for e in a[len(a) - k:]:
  if e < 0:
    n_ += 1
  pro_abs_ *= abs(e)
  pro_abs_ %= MOD
pro_ = (-1) ** n_ * pro_abs_ % MOD

if n % 2 == 0:
  print(pro_b)
  exit()

anses = []
last_posinb = None
last_neginb = None
for e in b:
  if e > 0:
    last_posinb = e
  if e < 0:
    last_neginb = e
first_posinc = None
first_neginc = None
for e in reversed(c):
  if e > 0:
    first_posinc = e
  if e < 0:
    first_neginc = e



if last_posinb is not None and first_neginc is not None:
  anses.append((-first_neginc / last_posinb, pro_b *
                modinv(last_posinb) * first_neginc % MOD))
if last_neginb is not None and first_posinc is not None:
  anses.append((-first_posinc / last_neginb, pro_b *
                modinv(last_neginb) * first_posinc % MOD))

if len(anses) != 0:
  print(max(anses)[1])
else:
  print(pro_)

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

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

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

a.sort(key=abs)

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

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        pos_ = []
        neg_ = []
        for x in a:
            if x >= 0:
                pos_.append(x)
            else:
                neg_.append(x)
        pos = deque(sorted(pos_, reverse=True))
        neg = deque((sorted(neg_)))
        while len(que) < k:
            if len(pos) >= 2:
                pp = pos[0] * pos[1]
            else:
                pp = -1
            if len(neg) >= 2:
                np = neg[0] * neg[1]
            else:
                np = -1
            if (pp > np) or len(que) == (k-1):
                que.append(pos.popleft())
            else:
                que.append(neg.popleft())
                que.append(neg.popleft())

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        b = [[] for _ in range(n)]
        for i in range(n):
            b[i] = [abs(a[i]), a[i]]
        b.sort(reverse=True)
        b = deque(b)
        que1 = deque()
        que2 = deque()
        sign = 1

        for i in range(k):
            val_abs, val = b.popleft()
            if val > 0:
                que1.append(val_abs)
            elif val < 0:
                que2.append(val_abs)
                sign *= -1
            else:
                print(0)
                return

        if sign == -1:
            add1, add2 = 0, 0
            rmv1, rmv2 = 10 ** 19, 10 ** 19
            if que1:
                rmv1 = que1[-1]
                for x_abs, x in b:
                    if x < 0:
                        add1 = x_abs
                        break
            if que2:
                rmv2 = que2[-1]
                for x_abs, x in b:
                    if x > 0:
                        add2 = x_abs
                        break

            if add1 == add2:
                print(0)
                return

            if add1 * rmv2 > add2 * rmv1:
                que2.append(add1)
                que1.pop()
            else:
                que1.append(add2)
                que2.pop()

        que.extend(que1)
        que.extend(que2)

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2
else:
    hugo = 1

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        if tmp % 2 == 1:
            tmp -= 1
            pl_num += 1
            tmp_ans = a[n-1]
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 0
                tmp_m_seki = 0
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                elif tmp_p_seki == 0 and tmp_m_seki == 0:
                    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])
    

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans % mod)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

mod = 10 ** 9 + 7

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

A.sort(reverse = True)

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

l = 0
r = N-1

ans = 1
if K % 2 == 1:
    ans *= A[0]
    l += 1

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

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
if n==k or max(a)<0 or min(a)>=0:
    if max(a)<0 and k%2==0:
        a.sort()
    else:
        a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
pos,neg=[],[]
for num in a:
    if num<0:
        neg.append(-num)
    else:
        pos.append(num)
neg.sort(reverse=True)
pos.sort(reverse=True)
nn=len(neg)
np=len(pos)
cand=[]
i,j=0,0
while k>0:
    if i<np-1 and j<nn-1:
        if k>=2:
            if pos[i+1]*pos[i]<neg[j+1]*neg[j]:
                cand.append(-neg[j+1])
                cand.append(-neg[j])
                k-=2
                j+=2
            else:
                cand.append(pos[i])
                k-=1
                i+=1
        else:
            cand.append(pos[i])
            k-=1
            i+=1
    elif j>=nn-1:
        cand.append(pos[i])
        k-=1
        i+=1
    elif i==np-1:
        if k==1:
            cand.append(pos[i])
            i+=1
            k-=1
        else:
            cand.append(-neg[j+1])
            cand.append(-neg[j])
            j+=2
            k-=2
    elif i==np:
        cand.append(-neg[j+1])
        cand.append(-neg[j])
        j+=2
        k-=2
for num in cand:
    ans*=num
    ans%=mod
print(ans)