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

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

if n == 1 and k == 1:
    print(al[0]%MOD)
    exit()

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

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

al_abs.sort(reverse=True)
if len(al_abs) < k:
    print(0)
    exit()

if len(al_abs) == k:
    ans = 1
    m_cnt = 0
    for a,s in al_abs:
        if s == -1: m_cnt += 1
        ans *= a
        ans %= MOD
    if m_cnt%2 == 0:
        print(ans)
    else:
        print(0)
    exit()
    

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



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

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





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


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



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


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

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




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

Solution (Python):
import sys

mod = 10 ** 9 + 7
N, K = map(int,input().split())
A = list(map(int,input().split()))
if all([a < 0 for a in A]):
    if K % 2 == 0:
        A.sort()
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
        print(ans)
        sys.exit()
    else:
        A.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
        print(ans)
        sys.exit()

A.sort()
l = 0
r = N - 1
ans = 1

if K % 2 == 1:
    ans *= A[r]
    ans %= mod
    r -= 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):
MOD = 10 ** 9 + 7

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

alst.sort()

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

if k == 1:
    print(alst[-1] % MOD)
    exit()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst = alst[::-1]
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True,key = lambda x:x[0])
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    elif blst[i][1] == 1:
        last_plus = blst[i][0]
    else:
        print(0)
        exit()
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    if blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if (flg_plus and flg_minus) or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus == k:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    elif minus_s == plus_s == 0:
        if next_minus == 0:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        else:
            print(0)
            exit()
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

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

s = sorted(a,reverse=True)
mod = 10**9 + 7
ans = 1

if k % 2 == 1 and s[0] < 0:
        for i in range(k):
            ans = ans * s[i] % mod
        print(ans)
        exit()

l = 0
r = n - 1



if k % 2 == 1:
  ans = ans * s[l]
  l += 1


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

print(ans)

Solution (Python):
mod=10**9+7
num,k=map(int,input().rstrip().split())
mai=list(map(int, input().rstrip().split()))
main=sorted(mai,key=abs,reverse=True)
result=1
def findplus_plus(x):
    for i in range(x,len(main)):
        if main[i]>=0:
            return main[i]
    return ''
def findplus_minus(x):
    for i in range(x,len(main)):
        if main[i]<0:
            return main[i]
    return ''
def findminus_plus(x):
    for i in range(x-1,-1,-1):
        if main[i]>=0:
            return main[i]
    return ''
def findminus_minus(x):
    for i in range(x-1,-1,-1):
        if main[i]<0:
            return main[i]
    return ''

if num==k:
    for i in main:
        result*=i
        result%=mod
elif sorted(main)[len(sorted(main))-1]<0:
    if (k%2)==0:
        for i in range(k):
            result*=main[i]
            result%=mod
    else:
        for i in range(len(main)-1,len(main)-1-k,-1):
            result*=main[i]
            result%=mod

else:
    count=0
    for i in range(k):
        if main[i]<0:
            count+=1
        result*=main[i]
        result%=mod
    if (count%2)==1:
        minplus=findminus_plus(k)
        minminus=findminus_minus(k)
        maxplus=findplus_plus(k)
        maxminus=findplus_minus(k)
        if type(maxplus)==type(''):
            plusplus=-1
            minusminus=minminus*maxminus
        else:
            if type(maxminus)==type('') or type(minplus)==type(''):
                minusminus=-1
                plusplus=0
            else:
                minusminus=minminus*maxminus
                plusplus=minplus*maxplus
        if plusplus>minusminus:
            main.remove(minminus)
            result=1
            for i in range(k-1):
                result*=main[i]
                result%=mod
            result*=maxplus
        elif plusplus<=minusminus:
            main.remove(minplus)
            result=1
            for i in range(k-1):
                result*=main[i]
                result%=mod
            result*=maxminus
            
print(result%mod)

Solution (Python):
from collections import defaultdict
def prod(A,k,mod):
  ans = 1
  for i in range(k):
      ans *= A[i]
      ans %= mod
  return ans
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  ans = 1
  if K==N:
    return prod(A,N,mod)
  minus = len([a for a in A if a<0])
  if minus==N:
    if K%2==0:
      A.sort()
    else:
      A.sort(reverse=True)
    return prod(A,K,mod)
  if K==1:
    return max(A)
  A.sort(key=lambda x:-abs(x))
  if A[K]==0:
    return 0
  minus = len([a for a in A[:K] if a<0])
  flag = [1]*K+[0]*(N-K)
  d = defaultdict(lambda: -1)
  if minus%2==1:
    for i in range(K,N):
      if A[i]>=0:
        d['p2'] = i
        break
    for i in range(K,N):
      if A[i]<0:
        d['m2'] = i
        break
    for i in range(K-1,-1,-1):
      if A[i]>0:
        d['p1'] = i
        break
    for i in range(K-1,-1,-1):
      if A[i]<0:
        d['m1'] = i
        break
    if d['p2']==-1 or d['m1']==-1:
      flag[d['m2']],flag[d['p1']] = 1,0
    elif d['m2']==-1 or d['p1']==-1:
      flag[d['p2']],flag[d['m1']] = 1,0
    elif A[d['p2']]*A[d['p1']]>A[d['m1']]*A[d['m2']]:
        flag[d['p2']],flag[d['m1']] = 1,0
    else:
      flag[d['m2']],flag[d['p1']] = 1,0
    ans = 1
    for i in range(N):
      if flag[i]==1:
        ans *= A[i]
        ans %= mod
    return ans
  return prod(A,K,mod)
print(solve())

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

s = sorted(a,reverse=True)
mod = 10**9 + 7
ans = 1

if k % 2 == 1 and s[0] < 0:
        for i in range(k):
            ans = ans * s[i] % mod
        print(ans)
        exit()

l = 0
r = n - 1
if k % 2 == 1:
  ans = ans * s[l]
  l += 1

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

print(ans)

Solution (Python):

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


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


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    MOD = 10**9 + 7

    num_zero = 0
    neg_list = []
    pos_list = []
    for a in A:
        if a == 0:
            num_zero += 1
        elif a < 0:
            neg_list.append(a)
        else:
            pos_list.append(a)

    
    if len(pos_list) + len(neg_list) < K:
        print(0)
    else:
        min_num_neg = K - len(pos_list)
        max_num_neg = min(K, len(neg_list))
        
        if min_num_neg == max_num_neg and min_num_neg % 2 == 1:
            if num_zero > 0:
                print(0)
                return

            ans = 1
            neg_list.sort()
            pos_list.sort(reverse=True)
            for i in range(K):
                use_pos = False
                if len(neg_list) == 0 or len(pos_list) == 0:
                    if len(neg_list) == 0:
                        use_pos = True
                    else:
                        use_pos = False
                elif abs(neg_list[-1]) < pos_list[-1]:
                    use_pos = False
                else:
                    use_pos = True

                if use_pos:
                    ans *= pos_list[-1]
                    pos_list.pop()
                else:
                    ans *= neg_list[-1]
                    neg_list.pop()

                ans %= MOD

            print(ans)

        else:
            
            ans = 1

            neg_list.sort(reverse=True)
            pos_list.sort()

            if K % 2 == 1:
                K -= 1
                ans *= pos_list[-1]
                pos_list.pop()

            
            for _ in range(0, K, 2):
                use_pos = False
                if len(neg_list) <= 1 or len(pos_list) <= 1:
                    if len(neg_list) <= 1:
                        use_pos = True
                    else:
                        use_pos = False
                elif abs(neg_list[-1] * neg_list[-2]) > (pos_list[-1] * pos_list[-2]):
                    use_pos = False
                else:
                    use_pos = True

                if use_pos:
                    ans *= pos_list[-1] * pos_list[-2]
                    pos_list.pop()
                    pos_list.pop()
                else:
                    ans *= neg_list[-1] * neg_list[-2]
                    neg_list.pop()
                    neg_list.pop()

                ans %= MOD

            print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce

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

mod = 10 ** 9 + 7
if n == k:
    print(reduce(lambda ac, v: ac * v % mod, a, 1))
    exit()

a.sort(key=lambda v: abs(v), reverse=True)
if len(list(filter(lambda v: v < 0, a))) == n and k % 2 == 1:
    print(reduce(lambda ac, v: ac * v % mod, a[n - k :], 1))
    exit()

ans = 1
mn = 0
for v in a[:k]:
    if v < 0:
        mn += 1
    ans *= abs(v)
    ans %= mod

if mn % 2 == 0:
    print(ans)
    exit()

mnp, mnn = 0, 0
for v in a[k - 1 :: -1]:
    if mnp != 0 and mnn != 0:
        break
    elif mnp == 0 and v > 0:
        mnp = v
    elif mnn == 0 and v < 0:
        mnn = v
mxp, mxn = 0, 0
for v in a[k:]:
    if mxp != 0 and mxn != 0:
        break
    elif mxp == 0 and v > 0:
        mxp = v
    elif mxn == 0 and v < 0:
        mxn = v
x, y = mxp, mnn
if mnp != 0 and mxn * mnn > mxp * mnp:
    x, y = mxn, mnp
ans *= pow(abs(y), mod - 2, mod)
ans %= mod
ans *= abs(x)
ans %= mod
print(ans)

Solution (Python):
from functools import reduce

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

a.sort(key=lambda v: abs(v), reverse=True)
mod = 10 ** 9 + 7
if n == k:
    print(reduce(lambda ac, v: ac * v % mod, a, 1))
    exit()
elif len(list(filter(lambda v: v < 0, a))) == n and k % 2 == 1:
    print(reduce(lambda ac, v: ac * v % mod, a[n - k :], 1))
    exit()

ans = 1
mn = 0
for v in a[:k]:
    if v < 0:
        mn += 1
    ans *= abs(v)
    ans %= mod

if mn % 2 == 0:
    print(ans)
    exit()

mnp, mnn = 0, 0
for v in a[k - 1 :: -1]:
    if mnp != 0 and mnn != 0:
        break
    elif mnp == 0 and v > 0:
        mnp = v
    elif mnn == 0 and v < 0:
        mnn = v
mxp, mxn = 0, 0
for v in a[k:]:
    if mxp != 0 and mxn != 0:
        break
    elif mxp == 0 and v > 0:
        mxp = v
    elif mxn == 0 and v < 0:
        mxn = v
x, y = mxp, mnn
if mnp != 0 and mxn * mnn > mxp * mnp:
    x, y = mxn, mnp
ans *= pow(abs(y), mod - 2, mod)
ans %= mod
ans *= abs(x)
ans %= mod
print(ans)

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

    mod = 10 ** 9 + 7
    n, k = map(int, input().split())
    pos, neg = [], []
    for x in map(int, input().split()):
        if x < 0:
            neg.append(x)
        else:
            pos.append(x)

    ans = 1
    neg.sort()
    pos.sort(reverse=True)
    neg_r = neg[::-1]
    lp, ln = len(pos), len(neg)

    if not pos and k & 1:
        for i in range(k):
            ans *= neg_r[i]
            ans %= mod
        print(ans)
        exit()

    x, y = 0, 0
    for i in range(k):
        if y >= ln:
            ans *= pos[x]
            ans %= mod
            x += 1
        elif x >= lp:
            ans *= neg[y]
            ans %= mod
            y += 1
        elif pos[x] >= -neg[y]:
            ans *= pos[x]
            ans %= mod
            x += 1
        else:
            ans *= neg[y]
            ans %= mod
            y += 1

    if n == k:
        print(ans)
        exit()

    if y & 1:
        ans_r = 1
        tmp1, tmp2 = -1, -1
        if y < ln and x != 0:
            tmp1 = neg[y] * neg[y - 1]
        if x < lp and y != 0:
            tmp2 = pos[x] * pos[x - 1]
        if tmp1 > tmp2:
            for i in range(x - 1):
                ans_r *= pos[i]
                ans_r %= mod
            for i in range(y + 1):
                ans_r *= neg[i]
                ans_r %= mod
        elif tmp1 <= tmp2:
            for i in range(x + 1):
                ans_r *= pos[i]
                ans_r %= mod
            for i in range(y - 1):
                ans_r *= neg[i]
                ans_r %= mod
        print(ans_r)
    else:
        print(ans % mod)


solve()

Solution (Python):
import sys
from collections import deque

import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()

    
    pp = int(bisect.bisect_left(A, 0))
    A_minus = deque(A[:pp])
    A_plus = deque(A[pp:])

    AA = deque([])
    AAm = deque([])
    if N == K:
        ans = 1
        for i in A:
            ans *= i
            ans %= mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(a1 * a2)

        for i in range(K // 2):
            if len(AAm) == 0:
                temp = AA.popleft()
            elif len(AA) == 0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp
            ans %= mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop()
            ans %= mod
        print(ans % mod)

    else:
        ans = A_plus.pop()

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(a1 * a2)

        for i in range(K // 2):
            if len(AAm) == 0:
                temp = AA.popleft()
            elif len(AA) == 0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp
            ans %= mod
        print(ans % mod)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
mod = 10**9+7

pos = []
neg = []
for a in As:
    if a>=0:
        pos.append(a)
    else:
        neg.append(a)
pos.sort(reverse=True)
neg.sort()
ans = 1
lenp, lenn = len(pos), len(neg)
if (lenp+lenn)==K:
    for a in As:
        ans *= a
        ans %= mod
    print(ans)
elif lenn==0:
    for i in range(K):
        ans *= pos[i]
        ans %= mod
    print(ans)
elif lenp==0:
    if K%2==0:
        for i in range(K):
            ans *= neg[i]
            ans %= mod
        print(ans)
    else:
        neg = neg[::-1]
        for i in range(K):
            ans *= neg[i]
            ans %= mod
        print(ans)        
else:
    p, n = 0, 0
    while p+n+1<K:
        if p+2<=lenp and n+2<=lenn:
            if pos[p]*pos[p+1]>=neg[n]*neg[n+1]:
                ans *= pos[p]
                p += 1
            else:
                ans *= neg[n]*neg[n+1]
                n += 2
        elif n+2<=lenn:
            ans *= neg[n]*neg[n+1]
            n += 2
        else:
            ans *= pos[p]
            p += 1
        ans %= mod
    if p+n<K:
        ans *= pos[p]
        ans %= mod
    print(ans)

Solution (Python):



import numpy

MAX = 10 ** 9 + 7

def prod_mod(la, mod):
  x = 1
  for a in la:
    x *= a
    x %= mod
  return x

def main():
  n, k = map(int, input().strip().split())
  la = numpy.array(list(map(int, input().strip().split())))
  la.sort()
  if n == k:
    print(prod_mod(la, MAX))
  else:
    if k % 2 == 1 and (la >= 0).sum() == 0:
      print(prod_mod(la[-k:], MAX))
    else:
      il, ir = 0, n-1
      cnt = 0
      l = []
      if k % 2 == 1:
        l.append(la[ir])
        ir -= 1
        cnt += 1
      while k - (cnt + 2) >= 0:
        if la[il] * la[il+1] > la[ir-1] * la[ir]:
          l.extend([la[il], la[il+1]])
          il += 2
        else:
          l.extend([la[ir-1], la[ir]])
          ir -= 2
        cnt += 2
      print(prod_mod(l, MAX))
      

if __name__=='__main__':
  main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = []
m = []
for a in A:
    if a < 0:
        m.append(abs(a))
    else:
        M.append(a)

i = 0
j = 0
tmp = 1
P = 10**9 + 7

if (K%2 == 0 and (len(m)//2*2 + len(M)//2*2) >= K) or (K%2 == 1 and (len(M) + len(m)//2*2) >= K and len(M) > 0):
    m.sort(reverse=True)
    M.sort(reverse=True)
    while K > 0:
        if K >= 2:
            if j+2 <= len(M) and i+2 <= len(m):
                if m[i]*m[i+1] < M[j]*M[j+1]:
                    tmp *= M[j]
                    j += 1
                    K -= 1
                else:
                    tmp *= m[i]*m[i+1]
                    i += 2
                    K -= 2
            elif j+2 <= len(M):
                tmp *= M[j]
                j += 1
                K -= 1
            elif i+2 <= len(m):
                tmp *= m[i]*m[i+1]
                i += 2
                K -= 2
            else:
                tmp *= m[i]*M[j]
        else:
            tmp *= M[j]
            K -= 1
        tmp %= P
else:
    m.sort()
    M.sort()
    for _ in range(K):
        if j+1 <= len(M) and i+1 <= len(m):
            if M[j] < m[i]:
                tmp *= M[j]
                j += 1
            else:
                tmp *= m[i]
                i += 1
        elif j+1 <= len(M):
            tmp *= M[j]
            j += 1
        else:
            tmp *= m[i]
            i += 1
        tmp %= P
    tmp *= -1
    tmp %= P
        
print(tmp)

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


mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now*=A[-i-1]%mod
        now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*= mi%mod
        ans%=mod
        l+=2
    else:
        ans*= pl%mod
        ans%=mod
        r-=2
print(ans%mod)

Solution (Python):


def solve(ls, k, debug=0):
    modulo = 10 ** 9 + 7
    n = len(ls)
    n_neg = 0
    for i in range(n):
        n_neg += ls[i] < 0
    n_pos = n - n_neg

    
    ls_abs = [abs(x) for x in ls]
    ls_abs_argsort = sorted(list(range(n)), key=lambda i: -ls_abs[i])

    
    if n_neg >= k:
        positive = (k % 2 == 0) or (n_pos > 0)
    else:
        positive = (n_neg % 2 == 0) or (n > k)

    
    if not positive:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[-1 - i]]
            p *= x
            p %= modulo
        return p

    
    
    
    
    
    
    

    
    s = 1
    for i in range(k):
        x = ls[ls_abs_argsort[i]]
        s *= -1 if x < 0 else 1

    
    if s > 0:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        return p

    
    
    
    opt1 = None
    opt2 = None
    neg1 = pos1 = None
    pos2 = neg2 = None

    
    swap_pos = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            pos1 = ls[ls_abs_argsort[i]]
            break

    swap_neg = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            neg1 = ls[ls_abs_argsort[i]]
            break

    if swap_pos is not None and swap_neg is not None:
        p = 1
        p *= ls[ls_abs_argsort[swap_pos]]
        p %= modulo
        for i in range(k):
            if i == swap_neg:
                continue
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        opt1 = p

    
    swap_pos = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            pos2 = ls[ls_abs_argsort[i]]
            break

    swap_neg = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            neg2 = ls[ls_abs_argsort[i]]
            break

    if swap_pos is not None and swap_neg is not None:
        p = 1
        p *= ls[ls_abs_argsort[swap_neg]]
        p %= modulo
        for i in range(k):
            if i == swap_pos:
                continue
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
            opt2 = p

    
    if opt1 is None:
        return opt2

    if opt2 is None:
        return opt1

    if pos1 * pos2 > neg1 * neg2:
        return opt1

    return opt2


def main(istr, ostr):
    n, k = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls, k)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Solution (Python):

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

MOD = 10 ** 9 + 7

if K % 2 == 1 and all(v < 0 for v in X):
    
    X.sort(key=lambda x: -x)
    ans = 1
    for i in range(K):
        ans = ans * X[i] % MOD
    print(ans)
elif K == N:
    ans = 1
    for i in range(K):
        ans = ans * X[i] % MOD
    print(ans)
else:
    pos = sorted(v for v in X if v >= 0)
    neg = sorted(-v for v in X if v < 0)

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

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

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

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

    print(ans)

Solution (Python):

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(a,k):
    a.sort()
    I = (np.abs(a)).argsort()
    a = a[I][::-1]
    if ( len(a) == k ): 
        return a
    if np.all( a<0 ):
        if ( k % 2 == 0 ):
            return a[:k]
        else:
            return a[-k:]
    p = a[a>=0]
    n = a[a<0]
    nums = [1]
    if k & 1:
        nums = [p[0]]
        p = p[1:]
        k -= 1
    if len(p) & 1:
        p = p[:-1]
    if len(n) & 1:
        n = n[:-1]
    p = p[::2] * p[1::2]
    n = n[::2] * n[1::2]
    a = np.concatenate([p,n])
    a.sort()
    a = a[::-1]
    return np.concatenate([nums,a[:k // 2]])

def main():
    n, k = map(int, readline().split())
    a = np.array(read().split(), np.int64)
    mod = 10**9 + 7
    b = solve(a,k).tolist()
    ans = 1
    for x in b:
        ans = ans * x % mod
    print(ans)

main()

Solution (Python):
import sys


def resolve(in_):
    n, k = map(int, in_.readline().split())
    a = list(map(int, in_.readline().split()))
    mod = 10 ** 9 + 7
    assert n == len(a)
    

    m = sorted(filter(lambda x: x < 0, a))
    p = sorted(filter(lambda x: x >= 0, a), reverse=True)

    if len(p) == 0:
        
        if k % 2:
            ans = m[-1] % mod
            for v in m[-k:-1]:
                v %= mod
                ans *= v
                ans %= mod
            return ans
        else:
            ans = m[0] % mod
            for v in m[1:k]:
                v %= mod
                ans *= v
                ans %= mod
            return ans
    elif len(m) == 0:
        ans = p[0] % mod
        for v in p[1:k]:
            v %= mod
            ans *= v
            ans %= mod
        return ans

    values = []
    p_index = 0
    m_index = 0
    for _ in range(k):
        if p_index < len(p) and m_index < len(m):
            if p[p_index] >= abs(m[m_index]):
                values.append(p[p_index])
                p_index += 1
            else:
                values.append(m[m_index])
                m_index += 1
        elif p_index >= len(p):
            values.append(m[m_index])
            m_index += 1
        elif m_index >= len(m):
            values.append(p[p_index])
            p_index += 1
        else:
            raise ValueError(f'{p_index=} {m_index=}')
    

    
    if any(v == 0 for v in values):
        return 0
    
    minus_values = sum(1 for v in values if v < 0)
    
    if minus_values > 0 and minus_values % 2:
        x = None
        y = None
        minus_max = max((value for value in values if value < 0), default=None)
        plus_min = min((value for value in values if value >= 0), default=None)
        if len(p) > p_index and minus_max:
            
            x = abs(p[p_index] + minus_max)
        if len(m) > m_index and plus_min:
            
            y = abs(m[m_index] + plus_min)
        
        if x is None and y is None:
            pass
        elif x is None or y is None:
            if x is None:
                values.remove(plus_min)
                values.append(m[m_index])
            elif y is None:
                values.remove(minus_max)
                values.append(p[p_index])
        else:
            if x < y:
                values.remove(minus_max)
                values.append(p[p_index])
            elif x > y:
                values.remove(plus_min)
                values.append(m[m_index])
            elif abs(minus_max) < plus_min:
                values.remove(plus_min)
                values.append(m[m_index]) 
            else:
                values.remove(minus_max)
                values.append(p[p_index])
               

    ans = values[0] % mod
    for v in values[1:k]:
        v %= mod
        ans *= v
        ans %= mod
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()