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

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2 == 1:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((P-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(M//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2 == 1:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero >= 1 and k%2 == 1:
    ans = 0
  else:
    if k%2 == 1:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero >= 1 and k%2 == 1:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2 == 1:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod

print(ans)

Solution (Python):
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Solution (Python):
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        bbb = aaa[:K]
    else:
        try:
            x1, y1 = min([a for a in aaa[-K:] if a > 0]), min([a for a in aaa[:-K] if a < 0])
        except:
            x1, y1 = 1, 0
        try:
            x2, y2 = max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0])
        except:
            x2, y2 = 1, 0
        bbb = aaa[-K:]
        if abs(x2 * y1) > abs(x1 * y2):
            bbb.remove(x1)
            bbb.append(y1)
        else:
            bbb.remove(x2)
            bbb.append(y2)
    print(prod(bbb, MOD))

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

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

    ans = 1
    nneg = 0
    a, b, c, d = -1, -1, -1, -1
    for k in range(K):
        ans = (ans * A[k])%MOD
        if A[k] < 0:
            nneg += 1
            b = k
        else:
            a = k
    
    if K == N or nneg%2 == 0:
        return ans
    
    for k in range(N-1, K-1, -1):
        if A[k] < 0:
            d = k
        else:
            c = k

    
    if a == -1 and c == -1: 
        ans = 1
        for k in range(K):
            ans = (ans * A[-1-k])%MOD
        return ans
    
    if a == -1 or d == -1:
        outn = A[b]
        inn = A[c]
    elif c == -1:
        outn = A[a]
        inn = A[d]
    else:
        if A[a]*A[c] > A[b]*A[d]:
            outn = A[b]
            inn = A[c]
        else:
            outn = A[a]
            inn = A[d]

    ans = (ans * pow(outn, MOD-2, MOD))%MOD
    ans = (ans * inn)%MOD
    return ans

if __name__ == "__main__":
    print(solve())

Solution (Python):
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 0: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD
        n //= 2

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

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

if N == K:
    if sign >= 0: print(ans)
    else: print(-ans % MOD)
    exit()

if sign < 0:
    out_neg, out_pos = 0, 0
    in_pos, in_neg = 0, 0

    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
            break
    

    if in_neg == 0 or out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    elif in_pos == 0 or out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    else:
        if out_pos * in_pos < out_neg * in_neg:
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Solution (Python):
n, k = [int(x) for x in input().strip().split(" ")]
p = 10**9 + 7

num_list = [int(x) for x in input().strip().split(" ")]
num_list = sorted(num_list, reverse = True)

ans = 1
l_idx = 0
r_idx = -1

if num_list[0] < 0 and k % 2 == 1:
  for i in range(k):
    ans = (ans * num_list[i]) % p
else:
  while True:
    if k >= 2:
      l_prod = num_list[l_idx] * num_list[l_idx+1]
      r_prod = num_list[r_idx] * num_list[r_idx-1]
      if l_prod >= r_prod:
        ans = (ans * num_list[l_idx]) % p
        l_idx +=1
        k -= 1
      else:
        ans = (ans * r_prod) % p
        r_idx -=2
        k -= 2
    elif k == 1:
      ans = (ans * num_list[l_idx]) % p
      ans %= p
      break
    else:
      break

print(ans)

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

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

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

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

if not plus:
    ans = 1
    if K % 2:
        
        for x in minus[-K:]:
            ans = (ans * x) % MOD
    else:
        
        for x in minus[:K]:
            ans = (ans * x) % MOD
    print(ans)
    exit()

idx = 0
for i in range(2, N, 2):
    if K - i < 0:
        break
    if not len(plus) >= K - i + 2:
        idx += 2
        continue
    if len(minus) >= i:
        if minus[i - 2] * minus[i - 1] < plus[K - i + 1] * plus[K - i]:
            break
        else:
            idx += 2

ans = 1
for x in minus[:idx] + plus[:K - idx]:
    ans = (ans * x) % MOD
print(ans)

Solution (Python):
import sys

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


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    res = 1
    if n == k:
        for a in A:
            res = (res * a) % mod
        print(res)
        exit()

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

    if len(P) == n:
        A.sort(reverse=True)
        for i in range(k):
            res = (res * A[i]) % mod
    elif len(M) == n:
        A.sort(reverse=True) if k % 2 else A.sort()
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort(reverse=True)
        M.sort()
        B = []
        if k % 2:
            k -= 1
            b = P.pop(0)
            B.append(b)
            res = (res * b) % mod
        for i in range(0, len(P), 2):
            if i + 1 < len(P):
                B.append(P[i] * P[i + 1])
        for j in range(0, len(M), 2):
            if j + 1 < len(M):
                B.append(M[j] * M[j + 1])
        B.sort(reverse=True)
        for i in range(k // 2):
            res = (res * B[i]) % mod

    print(res)

if __name__ == '__main__':
    resolve()

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

if n==k:
  
  ans=1
  for q in a:
    ans*=q
    ans%=mod
  print(ans)
  exit()
  
if all(q>=0 for q in a):
  
  ans=1
  a.sort()
  for _ in range(k):
    ans*=a.pop()
    ans%=mod
  print(ans)
  exit()

if all(q<0 for q in a):
  
  
  
  ans=1
  a.sort()
  if k%2==0:
    for i in range(k):
      ans*=a[i]
      ans%=mod
  else:
    for _ in range(k):
      ans*=a.pop()
      ans%=mod
  print(ans)
  exit()
  
pos=[]
neg=[]
for q in a:
  if q>=0:
    pos.append(q)
  else:
    neg.append(q)

pos.sort()
neg.sort()
neg=neg[::-1]


kk=k

if kk%2==1:
  ans=pos.pop()%mod
  kk=kk-1
else:
  ans=1



while kk>0:
  if len(pos)<2:
    ans=ans*neg.pop()%mod*neg.pop()%mod
    kk-=2
  elif len(neg)<2:
    ans=ans*pos.pop()%mod*pos.pop()%mod
    kk-=2
  else:
    if pos[-1]*pos[-2]>=neg[-1]*neg[-2]:
      ans=ans*pos.pop()%mod*pos.pop()%mod
      kk-=2
    else:
      ans=ans*neg.pop()%mod*neg.pop()%mod
      kk-=2
      
print(ans)

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

if n==k:
  ans=1
  for q in a:
    ans*=q
    ans%=mod
  print(ans)
  exit()
  
if all(q>=0 for q in a):
  ans=1
  a.sort()
  for _ in range(k):
    ans*=a.pop()
    ans%=mod
  print(ans)
  exit()

if all(q<0 for q in a):
  ans=1
  a.sort()
  if k%2==0:
    for i in range(k):
      ans*=a[i]
      ans%=mod
  else:
    for _ in range(k):
      ans*=a.pop()
      ans%=mod
  print(ans)
  exit()
  
pos=[]
neg=[]
for q in a:
  if q>=0:
    pos.append(q)
  else:
    neg.append(q)

pos.sort()
neg.sort()
neg=neg[::-1]

kk=k
if kk%2==1:
  ans=pos.pop()%mod
  kk=kk-1
else:
  ans=1

while kk>0:
  if len(pos)<2:
    ans=ans*neg.pop()%mod*neg.pop()%mod
    kk-=2
  elif len(neg)<2:
    ans=ans*pos.pop()%mod*pos.pop()%mod
    kk-=2
  else:
    if pos[-1]*pos[-2]>=neg[-1]*neg[-2]:
      ans=ans*pos.pop()%mod*pos.pop()%mod
      kk-=2
    else:
      ans=ans*neg.pop()%mod*neg.pop()%mod
      kk-=2
      
print(ans)

Solution (Python):
import sys




def solve(n, k, aaa):
    MOD = 10 ** 9 + 7

    if n == k:
        ans = 1
        for a in aaa:
            ans = ans * a % MOD
        return ans

    pos = []  
    neg = []
    for a in aaa:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

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

    pos.sort()
    neg.sort(reverse=True)
    ans = 1
    r = k

    if r % 2 == 1:
        ans = ans * pos.pop() % MOD
        r -= 1

    while r > 0:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pos.pop() * pos.pop() % MOD
            else:
                ans = ans * neg.pop() * neg.pop() % MOD
        r -= 2

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))

Solution (Python):
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
            res+=MOD
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np+1]*neg[k-np]):
        np-=2
        if len(neg)-1<k-np+1:
            break
    print((ruip[np]*ruin[k-np])%MOD)

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


def solve(N, K, A):
    ans = 1
    
    if K == N:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    
    else:
        
        A.sort(key=abs, reverse=True)
        
        sign = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
            if A[i] < 0:
                sign *= -1
            elif A[i] == 0:
                sign *= 0
        
        if sign < 0:
            small_nonneg = [a for a in A[K:] if a >= 0]
            small_neg = [a for a in A[K:] if a < 0]
            large_nonneg = [a for a in A[:K] if a >= 0]
            large_neg = [a for a in A[:K] if a < 0]
            if not small_neg or not large_nonneg:
                ans *= max(small_nonneg)
                ans %= MOD
                ans *= pow(max(large_neg), MOD - 2, MOD)
                ans %= MOD
            elif not small_nonneg or not large_neg:
                ans *= min(small_neg)
                ans %= MOD
                ans *= pow(min(large_nonneg), MOD - 2, MOD)
                ans %= MOD
            else:
                if min(small_neg) * max(large_neg) > max(small_nonneg) * min(
                    large_nonneg
                ):
                    
                    ans *= min(small_neg)
                    ans %= MOD
                    ans *= pow(min(large_nonneg), MOD - 2, MOD)
                    ans %= MOD
                else:
                    
                    ans *= max(small_nonneg)
                    ans %= MOD
                    ans *= pow(max(large_neg), MOD - 2, MOD)
                    ans %= MOD
    return ans


print(solve(N, K, A))

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
k_1=k
while k_1>1:
  if a[i]*a[i+1]>a[j]*a[j-1]:
    ans=ans*a[i]*a[i+1]%mod
    i+=2
    k_1-=2
  else:
    ans=ans*a[j]%mod
    j-=1
    k_1-=1
if k_1==1:
  ans=ans*a[j]%mod
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%mod
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
K=k

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)

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

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)

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

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                k -=1
            else:
                ans *=C.pop()*C.pop()
                k -=2
        elif len(B)>=2:
            ans *=B.pop()*B.pop()
            k -=2
        elif len(C)>=2:
            ans *=C.pop()*C.pop()
            k -=2
        else:
            k -=k
            flag=0
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1

    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = sorted(LI())

    r = 1
    i = n - 1
    j = 0
    if k % 2 == 1:
        r = a[i]
        i -= 1

    mf = r < 0

    for _ in range(k//2):
        t = a[i] * a[i-1]
        u = a[j] * a[j+1]
        if (not mf and t >= u) or (mf and t < u):
            r *= t
            r %= mod
            i -= 2
        else:
            r *= u
            r %= mod
            j += 2

    return r


print(main())

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

def prod(a):
    res = 1
    for x in a:
        res = (res * x) % MOD
    return res

def solve(n, k, a):
    if k == 1:
        return max(a)
    elif k == n:
        return prod(a)
    elif (max(a) < 0) and (k % 2 == 1):
        a = sorted(a, reverse=True)
        return prod(a[:k])
    else:
        a = sorted(a, key=lambda x: -abs(x))
        num_negative = len(list(filter(lambda x: x < 0, a[:k])))
        if num_negative % 2 == 0:
            return prod(a[:k])
        else:
            i1, j1 = None, None
            for i in range(k):
                if a[i] < 0:
                    i1 = i
            for j in range(k,n):
                if a[j] >= 0:
                    j1 = j
                    break
            i2, j2 = None, None
            for i in range(k):
                if a[i] >= 0:
                    i2 = i
            for j in range(k, n):
                if a[j] < 0:
                    j2 = j
                    break
            if (i1 is None) or (j1 is None):
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])
            elif (i2 is None) or (j2 is None):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            elif abs(a[j1] * a[i2]) > abs(a[i1] * a[j2]):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            else:
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])

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

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

def prod(a):
    res = 1
    for x in a:
        res = (res * x) % MOD
    return res

def solve(n, k, a):
    if k == 1:
        return max(a)
    elif k == n:
        return prod(a)
    elif (max(a) < 0) and (k % 2 == 1):
        a = sorted(a, reverse=True)
        return prod(a[:k])
    else:
        a = sorted(a, key=lambda x: -abs(x))
        num_negative = len(list(filter(lambda x: x < 0, a[:k])))
        if num_negative % 2 == 0:
            return prod(a[:k])
        else:
            i1, j1 = None, None
            for i in range(k):
                if a[i] < 0:
                    i1 = i
            for j in range(k,n):
                if a[j] >= 0:
                    j1 = j
                    break
            i2, j2 = None, None
            for i in range(k):
                if a[i] >= 0:
                    i2 = i
            for j in range(k, n):
                if a[j] < 0:
                    j2 = j
                    break
            if ((i1 is None) or (j1 is None)) and ((i2 is None) or (j2 is None)):
                return prod(a[:k])
            elif (i1 is None) or (j1 is None):
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])
            elif (i2 is None) or (j2 is None):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            elif abs(a[j1] * a[i2]) > abs(a[i1] * a[j2]):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            else:
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])

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

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

positives = [a for a in A if a > 0]
negatives = [a for a in A if a < 0]
positive_cnt = len(positives)
negative_cnt = len(negatives)
zero_cnt = A.count(0)


if 2 * min(K // 2, negative_cnt // 2) + positive_cnt >= K:
    ans = 1
    positives.sort(key=lambda x: abs(x), reverse=True)
    negatives.sort(key=lambda x: abs(x), reverse=True)

    if K % 2 == 1:
        ans *= positives.pop(0)
        K -= 1

    X = []
    for pair in zip(*[iter(positives)] * 2):
        X.append(reduce(operator.mul, pair, 1))
    for pair in zip(*[iter(negatives)] * 2):
        X.append(reduce(operator.mul, pair, 1))
    X.sort(reverse=True)

    ans *= reduce(lambda a, b: a * b % MOD, X[:K // 2], 1)
    print(ans % MOD)

elif zero_cnt:
    print(0)

else:
    A.sort(key=lambda x: abs(x))
    print(reduce(lambda a, b: a * b % MOD, A[:K], 1) % MOD)