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 functools

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

def multiply(x,y):
    ans = x*y
    if ans>=10**9+7 or ans<0:
        ans %= (10**9+7)
    return ans

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

if (A[-1]<0 and K%2==1):
    combi = A[-K:]
    if K >1:
        answer =  functools.reduce(multiply,combi)

elif K == N:
    answer = functools.reduce(multiply,A)

else:
    signs = 1
    i,j = 0,0
    for _ in range(K):
        if abs(A[i]) > abs(A[N-j-1]):
            signs *= sign(A[i])
            i += 1

        else:
            signs *= sign(A[N-j-1])
            j += 1
    combi = A[N-j:] + A[:i]
    del A[N-j:]
    del A[:i]
    combi = combi[::-1]

    if signs == -1:
        if A:
            if combi[-1]<0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]>=0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]<0 and A[-1] >0:
                if combi[0]*A[0] > combi[-1]*A[-1]:
                    del combi[-1]
                    combi.insert(0,A[0])
                else:
                    del combi[0]
                    combi.append(A[-1])
            elif A[-1] <= 0:
                del combi[-1]
                combi.insert(0,A[0])

    answer =  functools.reduce(multiply,combi)
print(answer)

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

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

Solution (Python):
import functools

def sign(x):
    if x>0:
        return 1
    elif x==0:
        return 0
    else:
        return -1
    
def multiply(x,y):
    ans = x*y
    if ans>=10**9+7 or ans<0:
        ans %= (10**9+7)
    return ans

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

if (A[-1]<0 and K%2==1):
    combi = A[-K:]
    if K >1:
        answer =  functools.reduce(multiply,combi)

elif K == N:
    answer = functools.reduce(multiply,A)
    
else:
    signs = 1
    i,j = 0,0
    for _ in range(K):
        if abs(A[i]) > abs(A[N-j-1]):
            signs *= sign(A[i])
            i += 1
            
        else:
            signs *= sign(A[N-j-1])
            j += 1
    combi = A[N-j:] + A[:i]
    del A[N-j:]
    del A[:i]
    combi = combi[::-1]     
       
    if signs == -1:
        if A:
            if combi[-1]<0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]>=0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]<0 and A[-1] >0:
                if combi[0]*A[0] > combi[-1]*A[-1]:
                    del combi[-1]
                    combi.insert(0,A[0])
                else:
                    del combi[0]
                    combi.append(A[-1])
            elif A[-1] <= 0:
                del combi[-1]
                combi.insert(0,A[0]) 
                
    answer =  functools.reduce(multiply,combi)
print(answer)

Solution (Python):
"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)

MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] >= a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] < a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)

Solution (Python):
"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)

MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] > a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] <= a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)

Solution (Python):
    
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==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):


Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    
    
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    
    
    
    
    
    if negative <= 1:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        if minus_value > 0:
            for b in B[K:]:
                if b[1] > 0:
                    ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                    if plus_value == 0:
                        plus_replaced_value = b[0]
                    else:
                        plus_replaced_value = plus_value*b[0]
                    break
        if plus_value > 0:
            for b in B[K:]:
                if b[1] < 0:
                    ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                    if minus_value == 0:
                        minus_replaced_value = b[0]
                    else:
                        minus_replaced_value = minus_value*b[0]
                    break
        if plus_replaced_value == 0 and minus_replaced_value == 0:
            pass
        elif plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
    
    
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):

import sys
from functools import reduce
from operator import mul
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = sorted((int(x) for x in input().split()), key=abs)
sgn = [0 if x == 0 else x // abs(x) for x in a]
M = 10**9 + 7
def modmul(x, y):
    return x * y % M
if reduce(mul, sgn[-k:]) >= 0:
    print(reduce(modmul, a[-k:], 1))
else:
    largest_unselected_neg = next(i for i, x in enumerate(reversed(a[:-k])) if x < 0) if any(x < 0 for x in a[:-k]) else None
    largest_unselected_pos = next(i for i, x in enumerate(reversed(a[:-k])) if x > 0) if any(x > 0 for x in a[:-k]) else None
    smallest_selected_neg = next(i for i, x in enumerate(a[-k:]) if x < 0) if any(x < 0 for x in a[-k:]) else None
    smallest_selected_pos = next(i for i, x in enumerate(a[-k:]) if x > 0) if any(x > 0 for x in a[-k:]) else None
    can1 = largest_unselected_neg is not None and smallest_selected_pos is not None
    can2 = largest_unselected_pos is not None and smallest_selected_neg is not None
    def ans1():
        return list(reversed(a[:-k]))[largest_unselected_neg] * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != smallest_selected_pos), 1) % M 
    def ans2():
        return list(reversed(a[:-k]))[largest_unselected_pos] * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != smallest_selected_neg), 1) % M
    if can1 and not can2:
        print(ans1())
    elif can2 and not can1:
        print(ans2())
    elif can1 and can2:
        if list(reversed(a[:-k]))[largest_unselected_neg] * a[-k:][smallest_selected_neg] > list(reversed(a[:-k]))[largest_unselected_pos] *  a[-k:][smallest_selected_pos]:
            print(ans1())
        else:
            print(ans2())
    else:
        print(reduce(modmul, a[:k], 1))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)



from collections import deque

import itertools
import heapq


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()
    A = deque(A)
    
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

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

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            heapq.heappush(AA, -a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            heapq.heappush(AA, -a1 * a2)
        ans = 1

        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA))
            ans %= mod
        print(ans % mod)

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

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            heapq.heappush(AA, -a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            heapq.heappush(AA, -a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
            ans %=mod
        print(ans% mod)


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappush, heappop
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,K = map(int, readline().split())
    A = [int(i) for i in readline().split()]

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

    plus = []
    minus = []

    for a in A:
        if a < 0:
            heappush(minus, a)
        else:
            heappush(plus, -a)

    if not plus:
        if K % 2 == 1:
            for _ in range(N-K):
                heappop(minus)
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        else:
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        print(ans)
        exit()

    p = []
    m = []
    for _ in range(K):
        if plus and minus:
            if plus[0] <= minus[0]:
                p.append(-heappop(plus))
            else:
                m.append(heappop(minus))
        elif plus:
            p.append(-heappop(plus))
        else:
            m.append(heappop(minus))

    for i in p:
        ans *= i
        ans %= MOD
    for j in m:
        ans *= j
        ans %= MOD

    if len(m) % 2 == 0:
        print(ans)

    else:
        if plus and minus and p and m:
            if p[-1] * (-plus[0]) >= m[-1] * minus[0]:
                ans *= pow(m[-1], MOD-2, MOD)
                ans *= -plus[0]
                ans %= MOD
            else:
                ans *= pow(p[-1], MOD-2, MOD)
                ans *= minus[0]
                ans %= MOD
        elif plus:
            ans *= pow(m[-1], MOD-2, MOD)
            ans *= -plus[0]
            ans %= MOD
        else:
            ans *= pow(p[-1], MOD-2, MOD)
            ans *= minus[0]
            ans %= MOD
        
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappush, heappop
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,K = map(int, readline().split())
    A = [int(i) for i in readline().split()]

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

    plus = []
    minus = []

    for a in A:
        if a < 0:
            heappush(minus, a)
        else:
            heappush(plus, -a)

    if not plus:
        if K % 2 == 1:
            for _ in range(N-K):
                heappop(minus)
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        else:
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        print(ans)
        exit()

    p = []
    m = []
    for _ in range(K):
        if plus and minus:
            if plus[0] <= minus[0]:
                p.append(-heappop(plus))
            else:
                m.append(heappop(minus))
        elif plus:
            p.append(-heappop(plus))
        else:
            m.append(heappop(minus))

    for i in p:
        ans *= i
        ans %= MOD
    for j in m:
        ans *= j
        ans %= MOD

    if len(m) % 2 == 0:
        print(ans)

    else:
        if plus and minus and p and m:
            if p[-1] * (-plus[0]) >= m[-1] * minus[0]:
                ans *= pow(m[-1], MOD-2, MOD)
                ans *= -plus[0]
                ans %= MOD
            else:
                ans *= pow(p[-1], MOD-2, MOD)
                ans *= minus[0]
                ans %= MOD
        elif plus:
            ans *= pow(m[-1], MOD-2, MOD)
            ans *= -plus[0]
            ans %= MOD
        else:
            ans *= pow(p[-1], MOD-2, MOD)
            ans *= minus[0]
            ans %= MOD
        
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls=sorted(ls, key=lambda x: -abs(x))


flag=[0 for _ in range(N)]

sign=0
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2

if sign==1: 
  
  swap_neg_to_pos=[]
  for i in range(K,N):
    if ls[i]<0:
      for j in range(K):
        if ls[K-1-j]>0:
          swap_neg_to_pos=[i,K-1-j,ls[K-1-j],-ls[i]]
          break
      break
  
  swap_pos_to_neg=[]
  for i in range(K,N):
    if ls[i]>0:
      for j in range(K):
        if ls[K-1-j]<0:
          swap_pos_to_neg=[i,K-1-j,-ls[K-1-j],ls[i]]
          break
      break

  
  if swap_neg_to_pos!=[] and swap_pos_to_neg!=[]: 
    
    if swap_neg_to_pos[2]*swap_pos_to_neg[3]<swap_pos_to_neg[2]*swap_neg_to_pos[3]: 
      flag[swap_neg_to_pos[0]]=1
      flag[swap_neg_to_pos[1]]=0
    else: 
      flag[swap_pos_to_neg[0]]=1
      flag[swap_pos_to_neg[1]]=0
  elif swap_neg_to_pos==[] and swap_pos_to_neg==[]: 
    flag.reverse()
  elif swap_pos_to_neg!=[]: 
    flag[swap_pos_to_neg[0]]=1
    flag[swap_pos_to_neg[1]]=0
  else:                     
    flag[swap_neg_to_pos[0]]=1
    flag[swap_neg_to_pos[1]]=0

ans=1
for i in range(N):
  if flag[i]==1:
    ans=(ans*ls[i])%MOD
print(ans)

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 = [[], []]
for i in range(n):
    if A[i] >= 0:
        B[0].append(A[i])
    else:
        B[1].append(A[i])
B[0].sort(reverse=True)
B[1].sort()

if k % 2 == 1 and len(B[0]) == 0:
    ans = 1
    ind = len(B[1])-1
    for i in range(k):
        ans = (ans * B[1][ind]) % mod
        ind -= 1
    print(ans)
elif k == n and len(B[1]) % 2 == 1:
    ans = 1
    for i in range(n):
        ans = (ans * A[i]) % mod
    print(ans)
else:
    k0 = min(len(B[0]), k)
    k1 = k-k0
    if k1%2==1:
        k0 -= 1
        k1 += 1
    
    while k1+1 < len(B[1]) and k0-2 >= 0 and B[1][k1]*B[1][k1+1] > B[0][k0-1]*B[0][k0-2]:
        k1 += 2
        k0 -= 2
        
        
    ans = 1
    for i in range(k0):
        ans = (ans * B[0][i]) % mod
    for i in range(k1):
        ans = (ans * B[1][i]) % mod
    print(ans)

Solution (Python):




def inf_product(xs):
    limit = int(1e9) + 7
    p = 1
    for x in xs:
        p *= x
        p %= limit
    return p

def calp():
    '''
    import random
    limit = int(1e9)
    n = int(2e5)
    k = int(n*9/10)
    x = []
    for i in range(n):
        x.append(random.randint(-limit,limit))
    '''
    n,k = map(int,input().split())
    x = list(map(int,input().split()))
    
    
    if n == k:
        return inf_product(x)
    
    if x.count(0) > n-k:
        return 0

    
    x.append(0)
    x.sort()
    
    m1 = x.index(0)
    m2 = x.count(0)
    x1 =x[:m1]
    x2 =x[m1+m2:]
    x3 =x[m1:m1+m2-1]
    

    
    
    
    if len(x2) == 0:
        if k%2 == 0:
            return inf_product(x1[:k])
        elif len(x3) != 0:
            return 0
        else:
            return inf_product(x1[-k:])

    
    p = 1
    if k%2 ==1:
        p *= x2[-1]
        x2.pop(-1)
        k -= 1

    x1b,x2b = [],[]
    for i in range(0,2*int(len(x1)/2),2):
        x1b.append(x1[i]*x1[i+1])
    x2.sort(reverse=True)
    for i in range(0,2*int(len(x2)/2),2):
        x2b.append(x2[i]*x2[i+1])
    
    x1b.extend(x2b)
    x1b.sort(reverse=True)
    x1b.insert(0,p)
    
    temp = int(k/2)

    if len(x1b) > temp:
        return inf_product(x1b[:int(k/2)+1])
    else:
        if len(x3) != 0:
            return 0
        else:
            return(-1)

print(calp())

Solution (Python):
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
pos, neg = [], []
for a in A:
    if a<0:
        neg.append(a)   
    else:
        pos.append(a)   
if pos:
    if N==K:    
        ok = (len(neg)%2 == 0)
    else:
        ok = True
else:
    ok = (K%2 == 0) 
ans = 1
if ok == False: 
    A.sort(key=abs)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    pos.sort()              
    neg.sort(reverse=True)  
    if K%2:
        ans *= pos.pop()    
    p = []  
    while len(pos)>=2:
        p.append(pos.pop() * pos.pop())
    while len(neg)>=2:  
        p.append(neg.pop() * neg.pop())
    p.sort(reverse=True)
    for i in range(K//2):   
        ans *= p[i]
        ans %= MOD
print(ans)

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

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])

if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= mod
    print(ans)
    exit()

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

cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                plus.appendleft(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            cou.append(p1)

        
for i in cou:
    ans *= i
    ans %= mod
print(ans)

Solution (Python):
M=10**9+7
n,k,*l=map(int,open(0).read().split())
lp,lm=[],[]
for i in l:
  if i<0: lm+=[i]
  else: lp+=[i]
cp,cm=len(lp),len(lm)
ok=0
if cp:
  if n==k: ok=1-cm%2
  else: ok=1
else: ok=1-k%2
a=1
if ok<1:
  l.sort(key=lambda x:abs(x))
  for i in range(k): a=a*l[i]%M
else:
  lp.sort()
  lm.sort(reverse=1)
  if k%2: a=lp.pop()
  p=[]
  while len(lp)>1: p+=[lp.pop()*lp.pop()]
  while len(lm)>1: p+=[lm.pop()*lm.pop()]
  p.sort(reverse=1)
  for i in range(k//2): a=a*p[i]%M
print(a)

Solution (Python):
M=10**9+7
n,k,*l=map(int,open(0).read().split())
lp,lm=[],[]
for i in l:
  if i<0: lm+=[i]
  else: lp+=[i]
cp,cm=len(lp),len(lm)
ok=0
if cp>0:
  if n==k: ok=1-cm%2
  else: ok=1
else: ok=1-k%2
a=1
if ok<1:
  l.sort(key=lambda x:abs(x))
  for i in range(k):
    a=a*l[i]%M
else:
  lp.sort()
  lm.sort(reverse=1)
  if k%2:
    a=lp.pop()
  p=[]
  while len(lp)>1:
    p+=[lp.pop()*lp.pop()]
  while len(lm)>1:
    p+=[lm.pop()*lm.pop()]
  p.sort(reverse=1)
  for i in range(k//2):
    a=a*p[i]%M
print(a)

Solution (Python):
def solve():
    can_positive = False
    if len(p) > 0:
        if k<n:
            can_positive = True
        else:
            can_positive = len(m) % 2 == 0
    else:
        can_positive=k%2==0
    if not can_positive:
        m.sort(reverse=True)
        return m[:k]+p
    p.sort()
    m.sort(reverse=True)
    a = [p.pop()] if k % 2 else [1]
    while len(p) >= 2:
        a.append(p.pop()*p.pop())
    while len(m) >= 2:
        a.append(m.pop()*m.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

mod = 10**9+7
n, k = list(map(int, input().split()))
m, p = [], []
for i in map(int, input().split()):
    if i < 0:
        m.append(i)
    else:
        p.append(i)
ans = 1
for i in solve():
    ans = ans * i % mod
print(ans)

Solution (Python):
    
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==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

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []

for Ai in A:
    if Ai>=0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(n)==N and K%2==1:
    n.sort(reverse=True)
    ans = 1
    
    for ni in n[:K]:
        ans *= ni
        ans %= MOD
    
    print(ans)
    exit()

if K==N and len(n)%2==1:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()
l = []

if K%2==1:
    ans = p[0]
    p = p[1:]
else:
    ans = 1
    
for i in range(len(p)//2):
    l.append(p[2*i]*p[2*i+1])
    
for i in range(len(n)//2):
    l.append(n[2*i]*n[2*i+1])
    
l.sort(reverse=True)
    
for li in l[:K//2]:
    ans *= li
    ans %= MOD
    
print(ans)

Solution (Python):
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n:
            can_positive = True
        else:
            can_positive = len(M) % 2 == 0
    else:
        can_positive = k % 2 == 0
    if not can_positive:
        return sorted(P + M, key=lambda x: abs(x))[:k]
    P.sort()
    M.sort(reverse=True)
    a = [P.pop()] if k % 2 else [1]
    while len(P) >= 2:
        a.append(P.pop() * P.pop())
    while len(M) >= 2:
        a.append(M.pop() * M.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k - k%2) // 2]

n, k = map(int, input().split())
P, M = [], []
for a in map(int, input().split()):
    if a < 0:
        M.append(a)
    else:
        P.append(a)
ans, mod = 1, 10 ** 9 + 7
for a in solve():
    ans *= a
    ans %= mod
print(ans)

Solution (Python):
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

ans=1
if (max(A)<=0 and k%2==1) or n==k:
    for i in range(k):
        ans=ans*A[n-1-i]%mod
else:
    mi=0
    pl=0
    flg=1
    for i in range(k):
        ans=ans*A[i]%mod
        if A[i]>0:
            pl=A[i]
        if A[i]<0:
            mi=A[i]
            flg*=-1
    if ans==0:
        pass
    elif flg==-1:
        mi2=None
        pl2=None
        for i in range(k,n):
            if A[i]>=0:
                pl2=A[i]
                break
        for i in range(k,n):
            if A[i]<=0:
                mi2=A[i]
                break
        can=0
        if mi!=0 and pl2 is not None and pl!=0 and mi2 is not None:
            if pl2*pl > mi2*mi:
                can = pow(mi,-1,mod)*pl2%mod
            else:
                can = pow(pl,-1,mod)*mi2%mod
        elif mi!=0 and pl2 is not None:
            can = pow(mi,-1,mod)*pl2%mod
        elif pl!=0 and mi2 is not None:
            can = pow(pl,-1,mod)*mi2%mod
        ans=ans*can%mod

print(ans)

Solution (Python):
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if not can_positive: return sorted(P+M, key=lambda x:abs(x))[:k]
    P.sort()
    M.sort(reverse=True)
    a = [P.pop()] if k%2 else [1]
    while len(P) >= 2: a.append(P.pop() * P.pop())
    while len(M) >= 2: a.append(M.pop() * M.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

n, k = map(int, input().split())
P, M = [], []
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
def solve():
    P.sort()
    M.sort(reverse = True)
    p, m = [], []
    while len(p) + len(m) < k:
        if len(P) > 0 and len(M) <= 0: p.append(P.pop())
        elif len(P) <= 0 and len(M) > 0: m.append(M.pop())
        elif P[-1] < -M[-1]: m.append(M.pop())
        else: p.append(P.pop())
    if len(m)%2:
        Mi = M.pop() if len(p)*len(M) else 1  
        Pi = P.pop() if len(m)*len(P) else -1 
        if Mi < 0 and Pi >= 0:
            if abs(p[-1] * Pi) < abs(m[-1] * Mi):
                p.pop()
                m.append(Mi)
            else:
                m.pop()
                p.append(Pi)
        elif Mi < 0:
            p.pop()
            m.append(Mi)
        elif Pi >= 0:
            m.pop()
            p.append(Pi)
        else:
            p = sorted(p+P+m+M, key=lambda x:abs(x))[:k]
            m = []
    return p + m

n, k = map(int, input().split())
P, M = [], [] 
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

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

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

mod=10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


b=[]
c=[]
for i in a:
    if i>=0:
        b.append(i)
    else:
        c.append(i)

b.sort(reverse=True)
c.sort()
ans=1
if k==n:
    for i in range(n):
        ans*=a[i]
        ans%=mod

elif k%2==1 and len(c)==n:
    c.sort(reverse=True)
    for i in range(k):
        ans*=c[i]
        ans%=mod

else:
    x=k
    
    v=0
    
    w=0
    if k%2==1:
        ans*=b.pop(0)
        k-=1

    for i in range(k):
        if x>=2:
            x-=2
            if v+2<=len(b) and w+2<=len(c):
                if b[v]*b[v+1]>c[w]*c[w+1]:
                    ans*=b[v]*b[v+1]
                    v+=2
                else:
                    ans*=c[w]*c[w+1]
                    w+=2


            elif v+2<=len(b):
                ans*=b[v]*b[v+1]
                v+=2

            else:
                ans*=c[w]*c[w+1]
                w+=2

            ans%=mod
            if x==0:
                break

print(ans)