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):
from collections import deque
rand = False
verbose = False

if rand:
    import random
    N, K = 200000, 10000
    A = random.choices(range(-10**9, 10**9), k=N)
else:
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

MOD = 10**9 + 7

def mul(A):
    ret = 1
    for i in range(len(A)):
        ret = (ret * A[i]) % MOD

    return ret

if K==N:
    print(mul(A))
    exit()

POS, NEG = list(), list()
for i in range(len(A)):
    if A[i] < 0:
        NEG.append(A[i])
    else:
        POS.append(A[i])

POS.sort(reverse=True)
NEG.sort()

if len(POS)==0 and K%2==1: 
    print(mul(NEG[-K:]))
    exit()

POS = deque(POS)
NEG = deque(NEG)

ans = list()
while len(ans)<K:
    if len(NEG) <= 1:
        if verbose: print('no more neg numbers')
        ans.append(POS.popleft()) 
    elif len(POS) <= 1:
        if verbose: print('no more pos numbers')
        if K-len(ans)>=2:
            ans.append(NEG.popleft())
            ans.append(NEG.popleft())
        else:
            ans.append(POS.popleft())
    elif POS[0]*POS[1] > NEG[0]*NEG[1] or K-len(ans)==1:
        if verbose: print('pos bigger')
        ans.append(POS.popleft())
    else:
        if verbose: print('neg biger')
        ans.append(NEG.popleft())
        ans.append(NEG.popleft())

print(mul(ans))

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

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
            ans %= MOD
        print(ans)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
            ans %= MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
res = 1
a.sort(reverse=True)
if a[0]<0 and k%2==1:
    for i in range(k):
        res = (res*a[i])%mod
else:
    right = n-1
    left = 0
    while k > 1:
        if a[right]*a[right-1] < a[left]*a[left+1]:
            res = (res*a[left])%mod
            left += 1
            k -= 1
        else:
            res = (res*a[right]*a[right-1])%mod
            right -= 2
            k -= 2
    if k == 1:
        res = (res*a[left])%mod

print(res)

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


N, K = read_values()
def main():
    A = read_list()
    

    A.sort(reverse=True)
    if N == K or (A[0] < 0 and K % 2 == 1):
        res = 1
        for a in A[:K]:
            res *= a
            res %= mod
        print(res)
        return

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

    P1 = list(filter(lambda a: a >= 0, A[:K]))
    P2 = list(filter(lambda a: a >= 0, A[K:]))
    N1 = list(filter(lambda a: a < 0, A[:K]))
    N2 = list(filter(lambda a: a < 0, A[K:]))

    if len(N1) % 2 == 1:
        
        if len(P1) == 0 or len(N2) == 0:
            N1[-1] = P2[0]
        elif len(P2) == 0:
            P1[-1] = N2[0]
        else:
            if P1[-1] * P2[0] >= N1[-1] * N2[0]:
                N1[-1] = P2[0]
            else:
                P1[-1] = N2[0]
    
    res = 1
    for p in P1:
        res *= p
        res %= mod

    for n in N1:
        res *= n
        res %= mod
    
    print(res % mod)
        

if __name__ == "__main__":
    main()

Solution (Python):
import io
import os
from heapq import merge

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

MOD = 10 ** 9 + 7


def solve(N, K, A):
    assert 1 <= K <= len(A)
    A.sort()
    neg = [-x for x in A if x < 0][::-1]  
    nonneg = [x for x in A if x >= 0]

    
    
    bestNeg = 1
    for i, x in enumerate(merge(neg, nonneg)):
        bestNeg *= x
        bestNeg %= MOD
        if i >= K - 1:
            break
    bestNeg = -bestNeg % MOD

    def getBestNonNeg(K):
        ans = 1
        if K % 2 == 1:
            
            if not nonneg:
                return None
            ans = nonneg.pop() % MOD
            K -= 1
        while K >= 2 and len(nonneg) >= 2 and len(neg) >= 2:
            if nonneg[-1] * nonneg[-2] < neg[-1] * neg[-2]:  
                ans = (ans * neg.pop() * neg.pop()) % MOD
            else:
                ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        while K >= 2 and len(neg) >= 2:
            ans = (ans * neg.pop() * neg.pop()) % MOD
            K -= 2
        while K >= 2 and len(nonneg) >= 2:
            ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        if K == 0:
            return ans
        return None

    
    ans = getBestNonNeg(K)
    if ans is not None:
        return ans
    
    return bestNeg


if False:
    from itertools import combinations
    import random

    random.seed(0)
    for t in range(10000000):
        N = random.randint(1, 10)
        A = [random.randint(-N, N) for i in range(N)]
        K = random.randint(1, N)
        ans = solve(N, K, A)
        expected = float("-inf")
        for combo in combinations(A, r=K):
            prod = 1
            for x in combo:
                prod *= x
            expected = max(expected, prod)
        print(N, K, A, ans, expected)
        assert ans == (expected % MOD)

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
print(solve(N, K, A))

Solution (Python):

"""

https://atcoder.jp/contests/abc173/tasks/abc173_e

クソだけどやろう

正負・0を分割

0がある場合は、最大を0に更新
0がN-K個より多い場合は即終了

残りの場合は、0を取らなくても構成できる場合のみ


"""

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

pl = []
mi = []
znum = 0

if K == 1:
    print (max(A))
    sys.exit()

for i in A:
    if i > 0:
        pl.append(i)
    elif i == 0:
        znum += 1
    else:
        mi.append(i)

ans = float("-inf")
if znum > 0:
    ans = 0


if znum > N-K:
    print (ans)
    sys.exit()




mod = 10**9+7
pl.sort()
mi.sort()

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

if K % 2 == 1 and len(pl) == 0:
    if znum > 0:
        ans = 0
    else:
        ans = 1
    mi.reverse()
    for i in range(K):
        ans *= mi[i]
        ans %= mod
    print (ans)
    sys.exit()




if K % 2 == 1:
    K -= 1
    ans = pl[-1]
    del pl[-1]
else:
    ans = 1

pl2 = []
pl.reverse()
if len(pl) % 2 == 1:
    pl.append(0)
if len(mi) % 2 == 1:
    mi.append(0)
for i in range(0,len(pl),2):
    pl2.append(pl[i] * pl[i+1])
for i in range(0,len(mi),2):
    pl2.append(mi[i] * mi[i+1])


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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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





N, K = getNM()
X = getList()

pos = sorted(v for v in X if v >= 0)
neg = sorted(-v for v in X if v < 0)


if N == K:
    ans = 1
    for x in X:
        ans *= x
        ans %= mod
    print(ans % mod)
    exit()

ok = False  
if pos:
    
    ok = True
else:
    
    ok = (K % 2 == 0)

ans = 1
if ok:
    
    if K % 2 == 1:
        
        
        
        ans = ans * pos.pop() % mod

    
    cand = []
    while len(pos) >= 2:
        x = pos.pop() * pos.pop()
        cand.append(x)

    while len(neg) >= 2:
        x = neg.pop() * neg.pop()
        cand.append(x)

    cand.sort(reverse = True) 
    
    for i in range(K // 2):
        ans = ans * cand[i] % mod
else:
    
    cand = sorted(X, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * cand[i] % mod

print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
from functools import reduce

def main():
    mod = 10 ** 9 + 7
    N, K = MI()
    A = LI()
    flag = 0
    for a in A:
        if a >= 0:
            flag = 1
            break

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

    if K == N:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        print(ans % mod)
        exit()
    elif flag == 0 and K % 2 != 0:
        B = A[::-1]
        ans = 1
        for i in range(K):
            ans *= B[i]
            ans %= mod
        ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        now_p = 0
        now_n = 0
        cnt_n = 0
        for i in range(K):
            a = A[i]
            ans *= a
            ans %= mod
            if a > 0:
                now_p = a
            elif a < 0:
                now_n = a
                cnt_n += 1
            else:
                print(0)
                exit()
        if cnt_n % 2 == 0:
            print(ans)
            exit()
        else:
            next_p = 0
            next_n = 0
            flag_p = 0
            flag_n = 0
            for i in range(K, N):
                a = A[i]
                if a > 0 and flag_p == 0:
                    next_p = a
                    flag_p = 1
                elif a < 0 and flag_n == 0:
                    next_n = a
                    flag_n = 1
                if flag_n == 1 and flag_p == 1:
                    break
                if a == 0:
                    break
        if now_p == 0:
            ans *= (pow(now_n, mod - 2, mod) * next_p) % mod
            ans %= mod
        elif next_p != 0 and next_n != 0:
            if now_p * next_p <= now_n * next_n:
                ans *= (pow(now_p, mod - 2, mod) * next_n) % mod
                ans %= mod
            else:
                ans *= (pow(now_n, mod - 2, mod) * next_p) % mod
                ans %= mod
        elif next_p == 0:
            ans *= (pow(now_p, mod - 2, mod) * next_n) % mod
            ans %= mod
        elif next_n == 0:
            ans *= (pow(now_n, mod - 2, mod) * next_p) % mod
            ans %= mod


        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from math import log
mod = int(1e9) + 7
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

def sign(v):
    if v == 0:
        return 0
    return 1 if v > 0 else -1

pref = [(0, 1)] * (n + 1)
suf = [(0, 1)] * (n + 1)

c = 1
sm = 0
sgn = 1
for j in range(n):
    c = c * a[j] % mod
    sgn *= sign(a[j])
    if a[j] != 0:
        sm += log(abs(a[j]))
    pref[j + 1] = (sgn * sm, c, sgn)

c = 1
sm = 0
sgn = 1
for j in range(n):
    c = c * a[n - j - 1] % mod
    sgn *= sign(a[n - j - 1])
    if a[n - j - 1] != 0:
        sm += log(abs(a[n - j - 1]))
    suf[j + 1] = (sgn * sm, c, sgn)

m = max(pref[k], suf[k])
for i in range(1, k):
    sgn = pref[i][2] * suf[k - i][2]
    pm = pref[i][1] * suf[k - i][1] % mod
    sm = abs(pref[i][0]) + abs(suf[k - i][0])
    m = max(m, (sgn * sm, pm, sgn))

    
print(m[1])

Solution (Python):
def make_set_list(array,valid):
    new_array = []
    for i in range(len(array)//2):
        new_array.append(array[2*i]*array[2*i+1])
    if len(array)%2 == 1 and valid == 1:
        new_array.append(array[len(array)-1])
    return new_array

N, K = list(map(int,input().split()))
As = list(map(int,input().split()))
p_nums = []
n_nums = []
for i in range(N):
    n = As[i]
    if n < 0:
        n_nums.append(n)
    else:
        p_nums.append(n)
As.sort(key = abs)
n_nums.sort()
p_nums.sort(reverse = True)
if len(p_nums) > 0:
    if N > K:
        ok = True
    elif len(n_nums) % 2 == 0:
        ok = True
    else:
        ok = False
elif K % 2 == 0:
    ok = True
else:
    ok = False

ans = 1

if ok:
    if K % 2 == 0:
        set_p_num = make_set_list(p_nums,1)
        set_n_num = make_set_list(n_nums,0)
        set_num = set_p_num + set_n_num
        set_num.sort(reverse = True)
        for i in range(K//2):
            ans = (ans*(set_num[i]%(10**9+7)))%(10**9+7)
    else:
        ans = p_nums.pop(0)
        set_p_num = make_set_list(p_nums,1)
        set_n_num = make_set_list(n_nums,0)
        set_num = set_p_num + set_n_num
        set_num.sort(reverse = True)
        for i in range(K//2):
            ans = (ans*(set_num[i]%(10**9+7)))%(10**9+7)
else:
    for i in range(K):
        ans = (ans*(As[i]%(10**9+7)))%(10**9+7)

print(ans)

Solution (Python):
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A:
    ans0 = ans0*a%MOD
  print(ans0)
  exit()

A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 = ans1*a%MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA = ansA*a%MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB = ansB*a%MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC = ansC*a%MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Solution (Python):
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A:
    ans0 = ans0*a%MOD
  print(ans0)
  exit()

A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 = ans1*a%MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Solution (Python):
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()

A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Solution (Python):
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()




B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2

if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Solution (Python):
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()
 
A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  


B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD


BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2

if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()





if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

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

    A.sort(reverse=True)  
    B = sorted(A, key=lambda x: abs(x), reverse=True)  
    C = []

    if k == n:
        C = A  
    elif k % 2 == 1 and A[0] < 0:
        C = A[:k]  
    else:
        plus = []
        minus = []
        for b in B[:k]:
            if b >= 0: plus.append(b)
            else: minus.append(b)

        if len(minus) % 2 == 1:
            
            rem1, add1, rem2, add2 = None, None, None, None

            rem1 = minus[-1]  
            add1 = max(B[k:])  
            valid1 = (add1 >= 0)

            valid2 = False
            if plus:
                rem2 = plus[-1]
                add2 = min(B[k:])  
                valid2 = (add2 < 0)

            if valid1 and valid2:
                if add1 * rem2 > rem1 * add2:
                    minus[-1] = add1
                else:
                    plus[-1] = add2
            elif valid1:
                minus[-1] = add1
            elif valid2:
                plus[-1] = add2

        C = plus + minus

    ans = 1
    for c in C:
        ans *= c
        if ans < 0: ans += mod
        ans %= mod
    print(ans)

if __name__ == '__main__':
    abc173_e()

Solution (Python):
from collections import deque

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

MOD = 10**9 + 7


X = []

Y = []


for a in A:
    if a >= 0:
        X.append(a)
    else:
        Y.append(a)
X.sort(reverse=True)
X = deque(X)
Y.sort()
Y = deque(Y)



nums = []

if K == N:
    nums = A


elif len(Y) == N and K % 2 == 1:
    for _ in range(K):
        nums.append(Y.pop())







else:
    while len(nums) < K:
        if len(X) >= 2 and len(Y) >= 2:
            if X[0] * X[1] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) >= 2 and len(Y) <= 1:
            nums.append(X.popleft())

        elif len(X) == 1 and len(Y) >= 2:
            if X[0] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) == 1 and len(Y) <= 1:
            nums.append(X.popleft())

        elif len(X) == 0 and len(Y) >= 2:
            if len(nums) == K - 1:
                
                
                nums.append(Y.pop())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        
        elif len(X) == 0 and len(Y) <= 1:
            num.append(Y.pop())

ans = 1
for num in nums:
    ans *= num
    ans %= MOD
print(ans)

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

X = []

Y = []
for a in A:
    if a >= 0:
        X.append(a)
    else:
        Y.append(a)
X.sort(reverse=True)
X = deque(X)
Y.sort()
Y = deque(Y)



nums = []

if K == N:
    nums = A


elif len(Y) == N and K % 2 == 1:
    for _ in range(K):
        nums.append(Y.pop())


else:
    while len(nums) < K:
        if len(X) >= 2 and len(Y) >= 2:
            if X[0] * X[1] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) >= 2 and len(Y) <= 1:
            nums.append(X.popleft())
        elif len(X) == 1 and len(Y) >= 2:
            if X[0] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) == 1 and len(Y) <= 1:
            nums.append(X.popleft())
        elif len(X) == 0 and len(Y) >= 2:
            if len(nums) == K - 1:
                nums.append(Y.pop())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) == 0 and len(Y) <= 1:
            num.append(Y.pop())

ans = 1
for num in nums:
    ans *= num
    ans %= MOD
print(ans)

Solution (Python):
def main():
    mod = 10**9+7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: -abs(x))
    kouho = []
    minus = 0
    last_plus = None
    last_minus = None
    if k == 1:
        print(max(a))
        return
    for i in range(k):
        kouho.append(a[i])
        if a[i] >= 0:
            last_plus = a[i]
        if a[i] < 0:
            minus += 1
            last_minus = a[i]
    if minus % 2 == 0:
        ans = 1
        for i in kouho:
            ans = ans*i % mod
        print(ans)
        return
    change_plus = None
    change_minus = None
    if last_plus != None:
        
        for i in range(k, n):
            if a[i] <= 0:
                change_plus = a[i]
                break
    if last_minus != None:
        
        for i in range(k, n):
            if a[i] >= 0:
                change_minus = a[i]
                break

    
    
    

    if change_plus == None and change_minus == None:
        ans = 1
        for i in range(k):
            ans = ans*a[-i-1] % mod
    elif change_plus == None:
        ans = change_minus
        for i in kouho:
            ans = ans*i % mod
        ans = ans*pow(last_minus, mod-2, mod) % mod
    elif change_minus == None:
        ans = change_plus
        for i in kouho:
            ans = ans*i % mod
        ans = ans*pow(last_plus, mod-2, mod) % mod
    else:
        if abs(change_plus*last_minus) < abs(change_minus*last_plus):
            ans = change_minus
            for i in kouho:
                ans = ans*i % mod
            ans = ans*pow(last_minus, mod-2, mod) % mod
        else:
            ans = change_plus
            for i in kouho:
                ans = ans*i % mod
            ans = ans*pow(last_plus, mod-2, mod) % mod
    print(ans)


main()

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
if N == K:
    for a in A:
        ans = ans * a % MOD
    print(ans)
    exit(0)

minus = []
plus = []
for a in A:
    if a < 0:
        minus.append(a)
    else:
        plus.append(a)

if len(minus) == N:
    if K % 2 == 0:
        A.sort()
    else:
        A.sort(reverse=True)
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans)
    exit(0)

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

if  K % 2:
    ans *= plus.pop()

B = []

while len(minus) > 1:
    a = minus.pop()
    b = minus.pop()
    B.append(a * b)

while len(plus) > 1:
    a = plus.pop()
    b = plus.pop()
    B.append(a * b)

B.sort()

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

print(ans)

Solution (Python):
N, K = map(int, input().split())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7
 
pos = sorted(v for v in X if v >= 0)
neg = sorted(-v for v in X if v < 0)
if N == K:
    ans = 1
    for x in X:
        ans *= x
        ans %= MOD
    print(ans % MOD)
    exit()
ok = False  
if pos:
    
    ok = True
else:
    
    ok = (K % 2 == 0)
 
ans = 1
if ok:
    
    if K % 2 == 1:
        
        
        
        ans = ans * pos.pop() % MOD
 
    
    cand = []
    while len(pos) >= 2:
        x = pos.pop() * pos.pop()
        cand.append(x)
 
    while len(neg) >= 2:
        x = neg.pop() * neg.pop()
        cand.append(x)
 
    cand.sort(reverse=True) 
    
    for i in range(K // 2):
        ans = ans * cand[i] % MOD
else:
    
    cand = sorted(X, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * cand[i] % MOD
 
print(ans)

Solution (Python):
def myabs(n):
    n = int(n)
    if n>0:
        return [n,1]
    else:
        return [abs(n),-1]


N,K = map(int,input().split())
A = list(map(myabs, input().split()))
A.sort(reverse=True)
Mod = 10**9+7

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= (a[i][0]*(-1))%mod
            ans %= mod
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        min_neg = -1
        min_pos = -1
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
                    min_neg = i
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
                min_pos = i
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag and n!=k:
            next_pos = -1
            next_neg = -1
            for i in range(k,n):
                if next_pos==-1 and a[i][1]==1:
                    next_pos = a[i][0]
                elif next_neg==-1 and a[i][1]==-1:
                    next_neg = a[i][0]
                if next_pos>=0 and next_neg>=0:
                    break
            if min_pos==-1:
                ans[0] *= next_pos%mod
                ans[0] %= mod
                print(ans[0])
            elif a[min_neg][0]*next_neg>a[min_pos][0]*next_pos:
                fin_ans = 1
                for i in range(k):
                    if i!=min_pos:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_neg%mod
                fin_ans %= mod
                print(fin_ans)
            else:
                fin_ans = 1
                for i in range(k):
                    if i!=min_neg:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_pos%mod
                fin_ans %= mod
                print(fin_ans)
        elif n==k and neg_flag:
            print((ans[1]*-1)%mod)
        else:
            print(ans[1])




if __name__=="__main__":
    main(N,K,A,Mod)