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())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()


P = []
M = []
for a in A:
    if a >= 0:
        P.append(a)
    elif a < 0:
        M.append(a)


if len(P) == 0 and K % 2 == 1:
    ans = 1
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()


P.sort(reverse=True)
M.sort()
LP = len(P)  
LM = len(M)  
cur_p = 0    
cur_m = 0    
cnt = 0      
ans = 1      
while cnt < K:  
    if K - cnt == 1 or LM - cur_m <= 1:  
        flag = 'p'
    elif LP - cur_p == 1:  
        if (K - cnt) % 2 == 1:  
            flag = 'p'
        else:                   
            flag = 'm'
    elif LP - cur_p == 0:  
        flag = 'm'
    else:  
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':  
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:  
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)

Solution (Python):


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

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

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
d = 1
m = 10**9+7
for i in range(n):
    if a[i] < 0:
        c.append(a[i])
    else:
        b.append(a[i])
b.sort()
c.sort(reverse=True)
if len(b) == 0 and k%2 == 1:
    for i in range(k):
        d = d*c[i]%m
else:
    while k > 0:
        if len(b) > 1 and len(c) > 1:
            if b[-1]*b[-2] < c[-1]*c[-2] and k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) == 1 and len(c) > 1:
            if k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) >= 1 and len(c) <= 1:
            d = d*b.pop()%m
            k -= 1
        else:
            d = d*c.pop()%m
            k -= 1
print(d)

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

ans = 1
if K == N:
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P = []
M = []
zero = 0
for a in A:
    if a >= 0:
        P.append(a)
    elif a < 0:
        M.append(a)


ans = 1
if len(P) == 0 and K % 2 == 1:
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()

P.sort(reverse=True)
M.sort()
S = 1
LP = len(P)
LM = len(M)
cur_p = 0
cur_m = 0
cnt = 0
ans = 1
while cnt < K:
    if K - cnt == 1 or LM - cur_m <= 1:
        flag = 'p'
    elif LP - cur_p == 1:
        if (K - cnt) % 2 == 1:
            flag = 'p'
        else:
            flag = 'm'
    elif LP - cur_p == 0:
        flag = 'm'
    else:
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)

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


P = []
M = []
zero = 0
for a in A:
    if a >= 0:
        P.append(a)
    elif a < 0:
        M.append(a)

ans = 1
if K == N:
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

ans = 1
if len(P) == 0 and K % 2 == 1:
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()

P.sort(reverse=True)
M.sort()
S = 1
LP = len(P)
LM = len(M)
cur_p = 0
cur_m = 0
cnt = 0
ans = 1
while cnt < K:
    if K - cnt == 1 or LM - cur_m <= 1:
        flag = 'p'
    elif LP - cur_p == 1:
        if (K - cnt) % 2 == 1:
            flag = 'p'
        else:
            flag = 'm'
    elif LP - cur_p == 0:
        flag = 'm'
    else:
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)

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

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

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

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

pos.sort(reverse=True)
neg.sort()

if len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
        ans %= MOD
    print(ans % MOD)
    exit()

if k % 2:
    ans *= pos.pop(0)
    k -= 1


l = []

for i in range(1, len(pos), 2):
    l.append(pos[i] * pos[i - 1])

for i in range(1, len(neg), 2):
    l.append(neg[i] * neg[i - 1])

l.sort(reverse=True)

for i in range(k // 2):
    ans *= l[i]
    ans %= MOD

print(ans % MOD)

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

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

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

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

pos.sort(reverse=True)
neg.sort()

if len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
        ans %= MOD
    print(ans % MOD)
    exit()

pi = 0
ni = 0
if k % 2:
    ans *= pos[pi]
    pi += 1
    k -= 1

while k > 0:
    if pi < len(pos) - 1:
        sp = pos[pi] * pos[pi + 1]
    else:
        sp = 0
    
    if ni < len(neg) - 1:
        sn = neg[ni] * neg[ni + 1]
    else:
        sn = 0
    
    if sp > sn:
        ans *= sp
        pi += 2
    else:
        ans *= sn
        ni += 2
    
    ans %= MOD
    k -= 2

print(ans % MOD)

Solution (Python):
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K = LI()
AS=LI()
AS.sort(reverse=True)
res = 1
if AS[0] >= 0 and AS[N-1] >= 0:
    for i in range(K):
        res *= AS[i]
        res %= DVSR
elif AS[0] > 0:
    if N != K:
        PS = []
        NS = []
        for i in AS:
            if i >= 0:
                PS.append(i)
            else:
                NS.append(-i)
        PS.sort(reverse=True)
        NS.sort(reverse=True)
        i = 0
        j = 0

        for k in range(K):
            if i < len(PS) and j < len(NS):
                if PS[i] > NS[j]:
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            else:
                if i < len(PS):
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            res %= DVSR
            
        
        if j % 2:
            if j < len(NS) and i < len(PS) and i > 0 and j > 0:
                if NS[j]*NS[j-1] > PS[i-1]*PS[i]:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            else:
                if j < len(NS) and i > 0:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            res %= DVSR
            
    else:
        for i in range(N):
            res *= AS[i]
            res %= DVSR
else: 
    if K % 2:
        v1 = 1
        v2 = 1
        for i in range(K):
            v1 *= AS[i]
            v1 %= DVSR
        res = v1
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR

print(res%DVSR)

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

MOD = 10 ** 9 + 7
ans = 1


if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)


elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= MOD
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    
    
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
     
    
    num = []
    for x, y in zip(pos[::2], pos[1::2]):
        num.append(x * y)
    for x, y in zip(neg[::2], neg[1::2]):
        num.append(x * y)

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    print(ans % MOD)

Solution (Python):
from collections import deque

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

MOD = 10 ** 9 + 7

n_minus = 0
for a in A:
    if a < 0:
        n_minus += 1

if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)

elif n_minus == N and K % 2 == 1:
    A = sorted(A, key=lambda x: 10 ** 9 if x == 0 else abs(x))

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

    print(ans)

else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    padding = None
    plus = deque()
    minus = deque()
    buf_p = deque()
    buf_m = deque()

    for a in A:
        if a >= 0:
            if padding is None and K % 2 == 1:
                padding = a
            else:
                buf_p.append(a)

                if len(buf_p) == 2:
                    plus.append(buf_p.popleft() * buf_p.popleft())
        else:
            buf_m.append(a)

            if len(buf_m) == 2:
                minus.append(buf_m.popleft() * buf_m.popleft())

    ans = 1
    if padding is not None:
        ans *= padding
        ans %= MOD

    for _ in range(K // 2):
        if len(plus) == 0:
            ans *= minus.popleft()
            ans %= MOD
        elif len(minus) == 0:
            ans *= plus.popleft()
            ans %= MOD
        elif plus[0] >= minus[0]:
            ans *= plus.popleft()
            ans %= MOD
        else:
            ans *= minus.popleft()
            ans %= MOD

    print(ans)

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=-1
      min_minus=1
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=-1
      max_minus=1
      for i in range(k,n):
        if arr[i]>=0 and max_plus==-1:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==1:
          max_minus=arr[i]
      if min_plus==-1:        
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      elif min_minus==1:        
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_minus
        ans%=mod
      elif min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_minus
        ans%=mod
      print(ans)

Solution (Python):
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))


pos_list = []
neg_list = []
zero_count = 0
for a_i in A:
    if a_i > 0:
        pos_list.append(a_i)
    elif a_i == 0:
        zero_count += 1
    else:
        neg_list.append(a_i)

lp = len(pos_list)
ln = len(neg_list)

if min(2 * (ln // 2), 2 * (K // 2)) + lp >= K:
    
    pos_list.sort(reverse = True)
    neg_list.sort()

    pos_twins = [pos_list[2 * i] * pos_list[2 * i + 1] for i in range(lp // 2)] + [0]
    neg_twins = [neg_list[2 * i] * neg_list[2 * i + 1] for i in range(ln // 2)] + [0]
    pos_twins.sort()
    neg_twins.sort()
 
    ans = 1
    pos_select = 0
    for i in range(K // 2):
        if pos_twins[-1] <= neg_twins[-1]:
            ans *= neg_twins[-1]
            ans %= mod
            neg_twins.pop()
        else:
            ans *= pos_twins[-1]
            ans %= mod
            pos_twins.pop()
            pos_select += 1
 
    if K % 2 == 1:
        if K == 1:
            ans = pos_list[2 * pos_select]
        else:
            ans *= pos_list[2 * pos_select]
    print(ans % mod)    
elif zero_count > 0:
	print(0)

else:
    ans = 1
    abs_list = sorted([abs(a) for a in A])
    for a in abs_list[:K]:
        ans *= a
        ans %= mod
    print((-1) * ans % mod)

Solution (Python):
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = float("inf")
    px = float("inf")
    m = float("inf")
    mx = float("inf")
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == float("inf"):
                p = ml[-1]
                px = x
        else:
            if pl and m == float("inf"):
                m = pl[-1]
                mx = x
        if m != float("inf") and p != float("inf"):
            if px * m > mx * p:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != float("inf"):
            ml.pop()
            pl.append(px)
        elif m != float("inf"):
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=-1
      min_minus=1
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=-1
      max_minus=1
      for i in range(k,n):
        if arr[i]>=0 and max_plus==-1:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==1:
          max_minus=arr[i]
      if min_plus==-1:        
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      elif min_minus==1:        
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_minus
        ans%=mod
      elif min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_minus
        ans%=mod
      print(ans)

Solution (Python):
import sys, math,os
from io import BytesIO, IOBase


from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

from decimal import Decimal
from fractions import Fraction
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')

INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
c=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    elif a1[i][1]<0:
        n1=i
        c*=-1
    else:
        c=0
    ans=(ans*a1[i][1])%mod
if c>=0:
    out(ans%mod)
else:
    b1=0
    b2=0
    for i in range(k,n):
        if a1[i][1]>=0 and b1==0:
            u1,v1=a1[n1][1],a1[i][1]
            b1=1
            c=1
        if a1[i][1]<0 and p!=-1 and b2==0:
            u2,v2=a1[p][1],a1[i][1]
            b2=1
            c=1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    else:
        if b1==1 and b2==1:
            if Fraction(v1,u1)<Fraction(v2,u2):
                ans=ans*pow(u1,mod-2,mod)*v1
            else:
                ans = ans * pow(u2, mod - 2, mod) * v2
        elif b1==1:
            ans = ans * pow(u1, mod - 2, mod) * v1
        else:
            ans = ans * pow(u2, mod - 2, mod) * v2
    out(ans%mod)

Solution (Python):
import heapq







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

MOD = 10**9+7


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

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)


if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()


pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if not neg:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if not pos:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

    if pos[0]<=neg[0]:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if pos[0]>neg[0]:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Solution (Python):






import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    
    
    
    
    
    
    
    


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

elif all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg: break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg: break

        
        
        
        
        
        

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest[rest_min_pos]
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest[rest_min_neg]
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_pos])
            v2 = abs(used[used_min_neg] * rest[rest_min_neg])
            if v1 > v2:
                used[used_min_neg] = rest[rest_min_pos]
            else:
                used[used_min_pos] = rest[rest_min_neg]

    for a in used:
        r = (r * a) % D

print(r)

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

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

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS%mod)
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS%mod)

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
absolute = deque(sorted(a, key=abs, reverse=True))

ans_lst = []

if k == n:
    ans_lst.extend(a)

elif len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())

else:
    minus_num = 0
    for _ in range(k):
        v = absolute.popleft()
        if v < 0:
            minus_num += 1
        ans_lst.append(v)
    if minus_num % 2 != 0:
        abs_min_plus_zero, abs_min_minus = None, None
        abs_max_plus_zero, abs_max_minus = None, None
        for i in ans_lst:
            if i >= 0:
                if abs_min_plus_zero is None:
                    abs_min_plus_zero = i
                else:
                    abs_min_plus_zero = min(i, abs_min_plus_zero)
            else:
                if abs_min_minus is None:
                    abs_min_minus = i
                else:
                    abs_min_minus = max(abs_min_minus, i)
        for i in absolute:
            if i >= 0:
                if abs_max_plus_zero is None:
                    abs_max_plus_zero = i
                else:
                    abs_max_plus_zero = max(i, abs_max_plus_zero)
            else:
                if abs_max_minus is None:
                    abs_max_minus = i
                else:
                    abs_max_minus = min(abs_max_minus, i)
        case1, case2 = False, False
        if abs_min_plus_zero is not None and abs_max_minus is not None:
            case1 = True
        if abs_min_minus is not None and abs_max_plus_zero is not None:
            case2 = True
        if case1 and case2:
            if abs_max_minus * abs_min_minus <= abs_max_plus_zero * abs_min_plus_zero:
                ans_lst.remove(abs_min_minus)
                ans_lst.append(abs_max_plus_zero)
            else:
                ans_lst.remove(abs_min_plus_zero)
                ans_lst.append(abs_max_minus)
        elif case1:
            ans_lst.remove(abs_min_plus_zero)
            ans_lst.append(abs_max_minus)
        elif case2:
            ans_lst.remove(abs_min_minus)
            ans_lst.append(abs_max_plus_zero)



ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)

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

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[n]*A[n+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if cnt == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*i%mod

print(ans)