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):
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
canPositive = 0
Positive = 0
ans = 1
def inv(arg):
    return pow(arg,mod-2,mod)
for i in range(N):
    if A[i] >= 0:
        Positive += 1
if N - K >= 1 and Positive >= 1:
    canPositive = 1
if Positive == 0 and K % 2 == 0:
    canPositive = 1
anslist = []
if canPositive:
    A.sort(key=lambda x:abs(x),reverse=True)
    n = 0
    for a in A[:K]:
        anslist.append(a)
        if a < 0:
           n += 1
    if n % 2 == 1:
        minpos = 0
        minneg = 0
        maxpos = 0
        maxneg = 0
        for i in anslist[::-1]:
            if i > 0:
                minpos = i
                break
        for i in anslist[::-1]:
            if i < 0:
                minneg = i
                break
        for i in A[K:]:
            if i < 0:
                maxneg = i
                break
        for i in A[K:]:
            if i > 0:
                maxpos = i
                break
        if maxneg == 0 or minpos == 0:
            ans *= maxpos*inv(minneg) 
        elif maxpos == 0 or minneg == 0:
            ans *= maxneg*inv(minpos) 
        else:
            if abs(minpos*maxpos) > abs(maxneg*minneg):
                ans *= maxpos*inv(minneg) 
            else:
                ans *= maxneg*inv(minpos) 
else:
    A.sort(key=lambda x:abs(x))
    for a in A[:K]:
        anslist.append(a)
for i in anslist:
    ans *= i
    ans %= mod
print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N, K = getlist()
	A = getlist()
	B = []
	for i in range(N):
		val = abs(A[i])
		if A[i] > 0:
			B.append([val , 1])
		elif A[i] < 0:
			B.append([val, -1])
		else:
			B.append([val, 0])
	B = sorted(B)

	if N == K:
		ans = 1
		for i in range(N):
			ans *= A[i]
			ans %= con
		print(ans)
		return

	M = 0; p = 0; m = 0; Aplus = []; Aminus = []; zerocnt = 0
	for i in A:
		if i == 0:
			zerocnt += 1
		elif i > 0:
			Aplus.append(i)
			M += 1; p += 1
		else:
			Aminus.append(i)
			M += 1; m += 1
	Aplus.sort()
	Aminus.sort()

	
	if K > M:
		print(0)
		return
	
	if zerocnt > 0 and M == m and K % 2 == 1:
		print(0)
		return
	
	if m == N:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			ans = 1
			for i in range(K):
				ans *= Aminus[-1 - i]
				ans %= con
			print(ans)
			return

	
	if m == M:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			print(0)
			return

	pindPre = -100; pindAfter = INF
	mindPre = -100;	mindAfter = INF
	

	for i in range(N - K):
		if B[i][1] == 1:
			pindPre = i
		elif B[i][1] == -1:
			mindPre = i

	for i in range(N - 1, N - K - 1, -1):
		if B[i][1] == 1:
			pindAfter = i
		elif B[i][1] == -1:
			mindAfter = i

	cnt = 0
	ans = 1
	for i in range(K):
		ans *= B[-1 - i][0]
		ans %= con
		if B[-1 - i][1] == -1:
			cnt += 1

	if cnt % 2 == 0:
		print(ans)
		return
	else:
		
		ans %= con
		if mindPre >= 0 and pindPre >= 0 and pindAfter <= N and mindAfter <= N:
			if B[mindPre][0] * B[mindAfter][0] <= B[pindPre][0] * B[pindAfter][0]:
				ans *= B[pindPre][0] * pow(B[mindAfter][0], con - 2, con)
				ans %= con
			else:
				ans *= B[mindPre][0] * pow(B[pindAfter][0], con - 2, con)
				ans %= con
			print(ans)
			return

		elif pindPre >= 0 and mindAfter <= N:
			ans *= B[pindPre][0] * pow(B[mindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return
		elif mindPre >= 0 and pindAfter <= N:
			ans *= B[mindPre][0] * pow(B[pindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return
		else:
			print(0)
			return


if __name__ == '__main__':
	main()

Solution (Python):
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
elif len(plist)==1:
    
    mlist.sort()
    if K%2==1:
        ans=plist[0]
    for i in range(K-1):
        ans=(ans*mlist[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    if len(plist)>0:
        pres=plist[len(plist)-1]
    if len(mlist)>0:
        mres=mlist[len(mlist)-1]
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    
    mapnum=K//2
    
    
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif (len(pmap)==0)and(len(mmap)>0):
            mi=mmap.popleft()
            ans = (ans *mi) % p
        elif (len(mmap)==0)and(len(pmap)>0):
            pl=pmap.popleft()
            ans = (ans *pl) % p
        else:
            ans=(ans*pres*mres)%p
    print(ans)

Solution (Python):
import math
import os 
def main(): 
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
 
    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-2:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod
 
        if k % 2 == 1:
            ret *= a[r]
            ret %= mod
 
    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod
 
    print(ret)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter, 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:
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    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)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        if len(plus) == 0:
            minus.pop()
            for a in A[K:]:
                if a >= 0:
                    plus.append(a)
                    break
        else:
            p = None
            m = None
            for a in A[K:]:
                if a >= 0 and p is None:
                    p = a
                if a < 0 and m is None:
                    m = a
                if p is not None and m is not None:
                    break

            if m is None:
                minus.pop()
                plus.append(p)
            elif p is None:
                plus.pop()
                minus.append(m)
            elif minus[-1] * m > plus[-1] * p:
                plus.pop()
                minus.append(m)
            else:
                minus.pop()
                plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)

Solution (Python):
import copy


def get_int():
    return int(input())


def get_string():
    return input()


def get_int_list():
    return [int(x) for x in input().split()]


def get_string_list():
    return input().split()


def get_int_multi():  
    return map(int, input().split())


def get_string_char_list():
    return list(str(input()))





'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort()
    m_list.sort(reverse=True)


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list.pop()
            k -= 1
        else:
            m_list.sort()
            ans = m_list.pop()
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list.pop() * m_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[-1] * p_list[-2]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[-1] * m_list[-2]
            else:
                mval = 0

            if pval > mval:
                p_list.pop()
                p_list.pop()
                ans = ans * pval % 1000000007
            else:
                m_list.pop()
                m_list.pop()
                ans = ans * mval % 1000000007
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 1
pls = 1
mod = 10**9+7
a_minu = [i for i in a if i <0]
if k==len(a):
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

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

else:
    ani= 0
    anj= 0
    tmp = 0
    tmp2  = 0
    alis = []
    lasim = -1
    lasip = -1
    for i in a:
        if i<0:
            alis.append([-i,-1])
        else:
            alis.append([i,1])
    alis.sort(key=lambda x:x[0], reverse=True)
    for i in range(k):
        if alis[i][1]==-1:
            lasim =  i
        else:
            lasip = i
        ans *= alis[i][0]
        ans %= mod
        pls *= alis[i][1]
    if pls ==1:
        print(ans)
    else:
        ju= 0
        jud = 0
        if lasim >= 0:
            tmp = ans*pow(alis[lasim][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==-1:
                    continue
                else:
                    
                    tmp *= alis[i][0]
                    ju = 1
                    ani = alis[i][0]
                    break
            if ju==0:
                tmp = 0
        if lasip >= 0:
            tmp2 = ans*pow(alis[lasip][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==1:
                    continue
                else:
                    
                    tmp2 *= alis[i][0]
                    jud = 1
                    anj = alis[i][0]
                    break
            if jud==0:
                tmp2 = 0

        if abs(alis[lasip][0]*ani)<=abs(alis[lasim][0]*anj):
            print(tmp2%mod)
        else:
            print(tmp%mod)

Solution (Python):
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%p
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%p
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)

Solution (Python):
import sys


def solve(n, k, aaa):
    pos = []
    neg = []
    MOD = 10 ** 9 + 7
    for a in aaa:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if len(pos) + len(neg) < k:
        return 0
    if len(pos) == 0:
        if k % 2 == 1:
            if len(neg) < n:
                return 0
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans
    if len(pos) + len(neg) == k:
        if n > k and len(neg) % 2 == 1:
            return 0
        ans = 1
        for a in pos:
            ans = ans * a % MOD
        for a in neg:
            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 >= 2:
        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 * pm % MOD
                pos.pop()
                pos.pop()
            else:
                ans = ans * nm % MOD
                neg.pop()
                neg.pop()
        r -= 2

    return ans


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

Solution (Python):
import copy


def get_int():
    return int(input())


def get_string():
    return input()


def get_int_list():
    return [int(x) for x in input().split()]


def get_string_list():
    return input().split()


def get_int_multi():  
    return map(int, input().split())


def get_string_char_list():
    return list(str(input()))





'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort()
    m_list.sort(reverse=True)


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list.pop()
            k -= 1
        else:
            m_list.sort()
            ans = m_list.pop()
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list.pop() * m_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[-1] * p_list[-2]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[-1] * m_list[-2]
            else:
                mval = 0

            if pval > mval:
                p_list.pop()
                p_list.pop()
                ans = ans * pval % 1000000007
            else:
                m_list.pop()
                m_list.pop()
                ans = ans * mval % 1000000007
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N==K:
    c=1
    for a in A:
        c*=a
        c%=mod

elif len(Ap)==0 and K%2:
    c=1
    while K :
        c*=Am.popleft()

        K-=1

        c%=mod
    c=-c
    c%=mod
    

else:
    
    c=1
    h=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[-1]>Ap[-1]:

                a=Am.pop()
                c*=a
                h+=1
            else:

                b=Ap.pop()
                c*=b

        elif Am:
            a=Am.pop()
            c*=a
            h+=1
        elif Ap:
            b=Ap.pop()
            c*=b
        K-=1
        c%=mod

    if h%2:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*a>Ap[-1]*b:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        elif Am and b!="unko":
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    p = 0
    m = 0
    for i in a:
        if i >= 0:
            p += 1
        else:
            m += 1
    f = 1
    for x in range(min(p,k)+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = []
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ans = 1
    if k&1:
        m = max(a)
        for i in range(n):
            if a[i] == m:
                break
        a = a[:i]+a[i+1:]
        ans *= m
        k -= 1
    for i in a:
        if i < 0:
            k1 ^= 1
            s *= -i
            if not k1:
                minus.append(s)
                s = 1
        else:
            k2 ^= 1
            s2 *= i
            if not k2:
                minus.append(s2)
                s2 = 1
    x = k>>1
    minus.sort(reverse = True)
    for m in minus[:x]:
        ans *= m
        ans %= mod
    print(ans%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

def solve():
    n, k = NextInts()
    da = NextIntList()
    ans = 1
    MOD = 10**9+7
    
    if n == k:
        for i in range(n):
            ans = ans*da[i]%MOD
        return ans
    
    neg = []
    pos = []
    for i in range(n):
        if da[i] < 0:
            neg.append(da[i])
        else:
            pos.append(da[i])
    neg.sort()
    pos.sort()

    if len(pos) == 0 and k%2 == 1:
        neg.reverse()
        for i in range(k):
            ans = ans * neg[i] % MOD
        return ans
    
    pos.reverse()
    li = []
    po, ne = 0, 0
    if k%2 == 1:
        po = 1
        ans = pos[0]
    while po+1 < len(pos):
        li.append(pos[po]*pos[po+1])
        po += 2
    while ne+1 < len(neg):
        li.append(neg[ne]*neg[ne+1])
        ne += 2
    li.sort()
    li.reverse()
    for i in range(k//2):
        ans = li[i] * ans % MOD
    return ans

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

Solution (Python):
n,k=map(int,input().split())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
mod=10**9+7
ans=1

if (k%2==0 or a[-1]>=0):
    mlt1=a[0]*a[1]
    mlt2=a[-2]*a[-1]
    l=0
    r=-1
    for i in range(k//2):
        if (mlt1>=mlt2):
            ans*=mlt1%mod
            l+=2
            if (l<=n-2):
                mlt1=a[l+1]*a[l]
        else:
            ans*=mlt2%mod
            r-=2
            if (r>=-n+1):
                mlt2=a[r-1]*a[r]
        ans%=mod
    if (k%2==1):
        ans*=a[r]
        ans%=mod
    
else:
    for i in range(k):
        ans*=a[n-1-i]
        ans%=mod
        
print(ans)

Solution (Python):
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    ans=1
    if m==0 or (m==n and k%2==1):
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n and k%2==0:
        for i in a[:k]:
            ans=(ans*i)%MOD
    else:
        ans=1
        l,r=0,-1
        lm=a[0]*a[1]
        rm=a[-1]*a[-2]
        for i in range(k//2):
            if lm>=rm:
                ans*=lm%MOD
                l+=2
                if l<=n-2:
                    lm=a[l]*a[l+1]
            else:
                ans*=rm%MOD
                r-=2
                if 1<=n+r:
                    rm=a[r]*a[r-1]
            ans%=MOD
        if k%2==1:
            ans*=a[r]
            ans%=MOD
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys, math
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x))[::-1]
P = int(1e9+7)
ans = 1
hu = None
sei = None
flg = False
for a in A:
    flg = a > 0
    if flg:
        break
if not flg:
    if K%2==1:
        for i in range(1, K+1):
            ans = (ans * A[-i]) % P
    else:
        for i in range(K):
            ans = (ans * A[i]) % P
    print(ans)
    sys.exit()
if K == N:
    for a in A:
        ans = (ans * a) % P
    print(ans)
    sys.exit()

for i, a in zip(range(K), A):
    if a > 0:
        if sei:
            ans = (ans * sei) % P
        sei = a
    else:
        if hu is None:
            hu = a
        else:
            ans = (ans * a * hu) % P
            hu = None

ptn1, ptn2 = -math.inf, -math.inf
if hu:
    if sei:
        for i in range(K, N):
            if A[i] > 0:
                ptn1 = sei * A[i]
                break
        for i in range(K, N):
            if A[i] <= 0:
                ptn2 = hu * A[i]
                break
        ans = (ans * max(ptn1, ptn2)) % P
    else:
        for i in range(K, N):
            if A[i] > 0:
                ans = (ans * A[i]) % P
                break
else:
    if sei:
        ans = (ans * sei) % P
print(ans % P)

Solution (Python):
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
p = []
m = []
ans = 1
for i in a:
    if i < 0:
        m.append(-i)
    else:
        p.append(i)
cp = len(p)
cm = len(m)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
p.sort()
m.sort()
p = deque(p)
m = deque(m)
if cm == n and k%2 == 1:
    f = 1
else:
    f = 0 
if f == 0:
    while k:
        
        if k%2 == 1 and cp:
            p1 = deque.pop(p)
            ans *= p1
            k -= 1
            cp -= 1
        elif f == 0 and m[-1] * m[-2] > p[-1] * p[-2] and cm > 1 and k>1:
            m1 = deque.pop(m)
            m2 = deque.pop(m)
            ans *= m1 * m2
            cm -= 2
            k -= 2
        elif cp > 0:
            p1 = deque.pop(p)
            ans *= p1
            k -= 1
            cp -= 1
        else:
            
            ans *= -m[2]
            m1 = deque.popleft(m)
            m2 = deque.popleft(m)
            m3 = deque.popleft(m)
            deque.appendleft(m,m1)
            deque.appendleft(m,m2)
            cm -= 1
            k -= 1
        ans %= mod
else:
    m1 = deque.popleft(m)
    m2 = deque.popleft(m)
    m1 = deque.popleft(p)
    m2 = deque.popleft(p)
    deque.append(m,10**10)
    deque.append(p,10**10)
    while k:
        k-=1
        
        if p[0] < m[0]:
            ans *= deque.popleft(p)
        else:
            ans *= -deque.popleft(m)
        ans %= mod

print(ans)

Solution (Python):
MOD = 1000000007
def maxProductSubarrayOfSizeK(A, n, k): 

	A.sort() 

	product = 1

	if (A[n - 1] == 0 and (k & 1)): 
		return 0

	if (A[n - 1] < 0 and (k & 1)): 
	    A.reverse()
	    for i in range(k):
	        product *= A[i]
	        if abs(product) >= MOD:
	            product = product%MOD
	    return product

	i = 0

	j = n - 1

	if (k & 1): 
		product *= A[j]
		product %= MOD
		j-= 1
		k-=1

	k >>= 1

	for itr in range( k) : 

		left_product = A[i] * A[i + 1] 

		right_product = A[j] * A[j - 1] 

		if (left_product > right_product) : 
			product *= left_product 
			product %= MOD
			i += 2
		
		else : 
			product *= right_product
			product %= MOD
			j -= 2

	return product 

n, k = map(int, input().split(' '))
numbers = [int(x) for x in input().split(' ')]
ans = maxProductSubarrayOfSizeK(numbers, n, k)

print((ans + MOD)%MOD)

Solution (Python):
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus=0
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      if prev_plus!=0:
        pick.remove(prev_plus)
        pick.append(prev_minus)
        pick.append(cand_minus)
      else:
        pick.append(cand_plus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

A = LIST()

plus0 = []
minus = []
zero = []

for a in A:
    if a >= 0:
        plus0.append(a)
    if a == 0:
        zero.append(a)
    if a < 0:
        minus.append(a)





if (len(minus) == N and K%2 == 1) or (plus0 and minus and N == K and len(minus)%2 == 1):
    
    if (len(minus) == N and K%2 == 1):
        minus.sort(reverse=True)  
        ans = 1
        for i in range(K):
            ans *= minus[i]
            ans %= mod
    else:
        ans = 1
        for x in minus+plus0:
            ans *= x
            ans %= mod
    print(ans)
else:
    if len(plus0) == N:
        ans = 1
        plus0.sort(reverse=True)
        for i in range(K):
            ans *= plus0[i]
            ans %= mod
        print(ans)
        exit()

    
    ans = 1
    cnt = 0
    plus0.sort()
    minus.sort(reverse=True)
    
    
    while cnt != K:
        if cnt == K-1 or len(minus) <= 1:
            ans *= plus0.pop()
            cnt += 1
        else:
            if not plus0:
                ans *= minus.pop()
                ans *= minus.pop()
                cnt += 2
            elif len(plus0) == 1:
                if plus0[0] > minus[-1]*minus[-2]:
                    ans *= plus0.pop()
                    cnt += 1
                else:
                    ans *= minus.pop()
                    ans *= minus.pop()
                    cnt += 2
            else:
                if plus0[-1]*plus0[-2] > minus[-1]*minus[-2]:
                    ans *= plus0.pop()
                    cnt += 1
                else:
                    ans *= minus.pop()
                    ans *= minus.pop()
                    cnt += 2
        ans %= mod
    print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = map(int, readline().split())
    A = list(map(int, readline().split()))
    MOD = int(1e9) + 7
    A.sort()
    ans = 1
    if A[n - 1] == 0 and (k & 1):
        ans = 0
    elif A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            ans = (ans * A[i]) % MOD
    else:
        i = 0
        j = n - 1
        if k & 1:
            ans = (ans * A[j]) % MOD
            j -= 1
            k -= 1
        k >>= 1
        for itr in range(k):
            left_product = A[i] * A[i + 1]
            right_product = A[j] * A[j - 1]
            if left_product > right_product:
                ans = (ans * left_product) % MOD
                i += 2
            else:
                ans = (ans * right_product) % MOD
                j -= 2

    print(ans % MOD)

if __name__ == '__main__':
    main()