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).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,k=map(int,input().split())
    a = [int(x) for x in input().split() if x!='0']
    fl=n-len(a)
    # print(fl)
    mod=10**9+7
    a.sort(key=lambda v:-abs(v))
    def ft(a):
        ans=1
        for x in a:
            ans=(ans*x)%mod
        return ans
    
    # print(a)
    def solve(a,k,fl):
        ans=1
        nv=1
        mx,mn=1,1
        for x in a:
            if k==0:
                break
            if x>0:
                ans=(ans*x)%mod
                k-=1
            if x<0:
                if nv!=1 and k>1:
                    k-=2
                    ans=(ans*x*nv)%mod
                    nv=1
                elif nv==1:
                    nv=x
        if k and fl:
            return (0,False)
        if k==1:
            return (ans,True)
        assert(k==0)
        return (ans,False)
    
    pv,nv=0,0
    for x in a:
        if x>0:
            pv+=1
        if x<0:
            nv+=1
    
    n=len(a)
    if k>n:
        print(0)
        exit(0)
    
    if k==n:
        if nv%2 and fl:
            print(0)
        else:
            print(ft(a))
        exit(0)
    
    if nv==0:
        print(ft(a[:k]))
        exit(0)
    
    if pv==0 and k%2==0:
        print(ft(a[:k]))
        exit(0)
    
    if pv==0 and k%2:
        if fl:
            print(0)
        else:
            a=a[::-1]
            print(ft(a[:k]))
        exit(0)
    
    ans=solve(a,k,fl)
    if ans[1]:
        a=a[::-1]
        ans=solve(a,k,fl)
    print(ans[0])
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

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

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

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

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

if B==[]:
    ANS=1
    for i in range(K):
        ANS=ANS*(C[i])%mod

    if Z==[] and K%2==0:
        print(ANS)
    elif Z==[] and K%2==1:
        print(-ANS%mod)
    elif K%2==1:
        print(0)
    else:
        print(ANS)

    sys.exit()

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

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

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

    print(S%mod)

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

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

        ind=K-len(B)

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

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

        ind=K-len(B)+1
        

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

    print(S%mod)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9 + 7


def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def abs_prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod


N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove = None
add = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None:
            remove = last_minus
            add = i
            sig = 1
            break
        elif A[i] < 0 and last_plus != None:
            remove = last_plus
            add = i
            sig = 1
            break
        elif A[i] == 0:
            sig = 0
            break

if sig == 0:
    print(0)
elif sig > 0:
    ap = abs_prod(A, K, add, remove)
    print(ap)
else:
    ap = abs_prod(A[::-1], K, add, remove)
    print((MOD - ap) % MOD)

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo > re:
      ans *= fo 
      ans %= mod
      i += 2
    elif (A[j - 1] < 1) or (A[j - 2] < 1):
      ans *= fo 
      ans %= mod
      i += 2      
    else:
      ans *= re
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def rev(i):
    ni = i
    ans = 1
    t = 10**9+5
    mod = 10**9+7
    while t > 0:
        if t&1:
            ans = (ans*ni)%mod
        t >>= 1
        ni = (ni**2)%mod
    return ans

def main():
    n,k = map(int,ipt().split())
    a = [(abs(int(i)),int(i)) for i in ipt().split()]
    Mi = 10**9
    Ma = -10**9
    mod = 10**9+7
    a.sort(reverse=True)
    if n == k:
        ans = 1
        for i in a:
            ans = (ans*i[1])%mod
        print(ans)
        exit()
    for i in a:
        if Ma < i[1]:
            Ma = i[1]
        if Mi > i[1]:
            Mi = i[1]
    if Ma < 0 and k&1:
        ans = 1
        for i,ai in enumerate(a[::-1]):
            ans = (ans*ai[0])%mod
            if i == k-1:
                break
        print((-ans)%mod)
        exit()
    pp = None
    pm = None
    ans = 1
    s = 1
    for i,ai in enumerate(a[:k:]):
        ans = ans*ai[0]%mod
        if ai[1] == 0:
            print(0)
            exit()
        elif ai[1] > 0:
            pp = ai[0]
        else:
            pm = ai[0]
            s *= -1
    if s == 1:
        print(ans)
        exit()
    np = 0
    nm = 0
    for ai in a[k::]:
        if ai[1] > 0 and not np:
            np = ai[0]
        elif ai[1] < 0 and not nm:
            nm = ai[0]
        if np and nm:
            break
    if pp == None:
        print(0)
    elif nm == None and np == None:
        print(0)
    elif nm == None:
        print(ans*rev(pm)*np%mod)
    elif np == None:
        print(ans*rev(pp)*nm%mod)
    else:
        if nm*pm < np*pp:
            print(ans*rev(pm)*np%mod)
        else:
            print(ans*rev(pp)*nm%mod)



    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()
minus = [a for a in A if a < 0][::-1]
plus = [a for a in A if a > 0][::-1]

prod = lambda x,y : ((x*y) % MOD)


if K % 2 == 1 and len(plus) == 0:
    if 0 in A:
        print(0)
    else:
        ans = reduce(prod,minus[:K])
        print(ans % MOD)
    exit()

ans = 1
if K % 2 == 1:
    ans *= plus[0]
    plus2 = [p*q for p,q in zip(plus[1::2],plus[2::2])]
    minus2 = [p*q for p,q in zip(minus[:-1:-2],plus[:-2:-2])]
    cand = sorted((plus2 + minus2),reverse=True)
    ans *= reduce(prod,cand[:K//2],1)
    ans %= MOD
else:
    plus2 = [p*q for p,q in zip(plus[::2],plus[1::2])]
    minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
    cand = sorted((plus2 + minus2),reverse=True)
    ans *= reduce(prod,cand[:K//2],1)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
n, k = get_ints()
li = get_list()
pos = []
neg = []
zeroes = 0
for i in li:
    if i < 0: neg.append(i)
    elif i > 0: pos.append(i)
    else: zeroes += 1
lengthOfPos, lengthOfNeg = len(pos), len(neg)
if lengthOfNeg + lengthOfPos < k :
    print("0")
elif (k - lengthOfPos) & 1:
    if zeroes:
        print("0")
    else:
        try: ans = reduce(lambda x, y: (x*y) % UGLYMOD, pos)
        except: ans = 1
        neg.sort(reverse = True)
        # print(neg)
        for i in range(k-lengthOfPos):
            ans  = (ans * neg[i]) % UGLYMOD
        print(ans)
else:
    pos.sort(reverse = True); positionOfPos = 0
    neg.sort(); positionOfNeg = 0
    if lengthOfNeg & 1:
        neg.pop()
        lengthOfNeg -= 1
    ans = 1
    while k > 1:
        try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
        except: negpower = -float('inf')
        try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
        except: pospower = -float('inf')
        if pospower >= negpower:
            positionOfPos += 2
            ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
        else:
            ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
            positionOfNeg += 2
        k -= 2
    if k == 1:
        ans = (ans * pos[positionOfPos]) % UGLYMOD
    print(ans)







'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    A.sort(key=abs, reverse=True)

    ans = 1
    sgn = 1
    last_minus_in_k = None
    last_plus_in_k = None
    first_minus_outof_k = None
    first_plus_outof_k = None
    for i, x in enumerate(A):
        if i < K:
            if x < 0:
                sgn = -sgn
                last_minus_in_k = x
                ans = (ans * (-x)) % MOD
            else:
                last_plus_in_k = x
                ans = (ans * x) % MOD
        else:
            if x < 0:
                if first_minus_outof_k is None:
                    first_minus_outof_k = x
            else:
                if first_plus_outof_k is None:
                    first_plus_outof_k = x

    if sgn == 1 or K == N:
        print(ans % MOD)
        return

    # 交換できる場合
    if last_plus_in_k is None:
        # マイナスが奇数個のみ
        if first_plus_outof_k is not None:
            ans = ((ans * pow(last_minus_in_k, MOD - 2, MOD)) % MOD) * first_plus_outof_k % MOD
            print(ans % MOD)
            return

        A.sort(key=abs)
        ans = 1
        sgn = 1
        for i, x in enumerate(A):
            if i < K:
                if x < 0:
                    sgn = -sgn
                    ans = (ans * (-x)) % MOD
                else:
                    ans = (ans * x) % MOD
            else:
                break
        print(ans * sgn % MOD)
        return

    else:
        if first_plus_outof_k is not None and first_minus_outof_k is not None:
            if first_minus_outof_k * last_minus_in_k >= first_plus_outof_k * last_plus_in_k:
                ans = ((ans * pow(last_plus_in_k, MOD - 2, MOD)) % MOD) * first_minus_outof_k % MOD
                print(ans % MOD)
                return
            else:
                ans = ((ans * pow(last_minus_in_k, MOD - 2, MOD)) % MOD) * first_plus_outof_k % MOD
                print(ans % MOD)
                return

        if first_plus_outof_k is not None:
            ans = ((ans * pow(last_minus_in_k, MOD - 2, MOD)) % MOD) * first_plus_outof_k % MOD
            print(ans % MOD)
            return

        if first_minus_outof_k is not None:
            ans = ((ans * pow(last_plus_in_k, MOD - 2, MOD)) % MOD) * first_minus_outof_k % MOD
            print(ans % MOD)
            return


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
a = lr()
a.sort()
mnum = 0
znum = 0
mlist = []
plist = []
judge = []
for num in a:
    if num < 0:
        mnum += 1
        mlist.append(abs(num))
    elif num == 0:
        znum += 1
    else:
        plist.append(num)
    judge.append(abs(num))
mflag = False
if (a[-1] <= 0 and k%2 == 1) or (k == n and mnum%2 == 1):
    mflag = True
if ((0 in a) and ((mflag) or (n-znum-k < 0))):
    print(0)
    sys.exit()
mmlist = []
for i in range(1,len(mlist),2):
    mmlist.append(mlist[i-1]*mlist[i]%mod)
plist.reverse()
mind = 0
pind = 0
pmax = len(plist)
mmax = len(mlist)
if k%2 == 0:
    if pmax%2 == 1:
        pmax-=1
else:
    if pmax%2 == 0:
        pmax = max(pmax-1,0)
tmp = 0
ans = 1
if not mflag:
    while tmp < k:
        if k-tmp == 1:
            ans *= plist[pind]
            ans %= mod
            tmp+=1
            pind+=1
        else:
            if pind+1 < pmax:
                if mind < mmax and mmlist[mind] > plist[pind]*plist[pind+1]:
                    ans *= mmlist[mind]
                    ans %= mod
                    tmp += 2
                    mind+=1
                else:
                    ans *= plist[pind]
                    ans %= mod
                    tmp += 1
                    pind+=1
            elif pind < pmax:
                if mind < mmax and mmlist[mind] > plist[pind]:
                    ans *= mmlist[mind]
                    ans %= mod
                    tmp += 2
                    mind+=1
                else:
                    ans *= plist[pind]
                    ans %= mod
                    tmp += 1
                    pind+=1
            else:
                ans *= mmlist[mind]
                ans %= mod
                tmp += 2
                mind += 1
    print(ans)
else:
    judge.sort()
    for i in range(k):
        ans *= judge[i]
        ans %= mod
    print((-ans)%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

pos = []
nag = []
pn = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
        pn.append((A[i], True))
    elif A[i] < 0:
        nag.append(A[i])
        pn.append((-A[i], False))
    else:
        zero += 1

pos.sort()
nag.sort(reverse=True)
pn.sort()

# hard case work
if N - zero < K:
    print(0)

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

elif not pos:
    ans = 1
    if K & 1:
        for i in range(K):
            ans *= nag[i]
            ans %= MOD
    else:
        for i in range(K):
            ans *= nag[-i-1]
            ans %= MOD
    print(ans)



# nagative and positive
else:
    # large first
    arr = []

    for i in range(K):
        if not pos: break
        arr.append(pos.pop())

    while len(arr) < K:
        arr.append(1)

    ans = 1

    while arr:
        if len(arr) == 1:
            ans *= arr[0]
            ans %= MOD
            break

        a = arr.pop()
        b = arr.pop()
        if len(nag) < 2:
            ans *= a
            ans %= MOD
            ans *= b
            ans %= MOD
        else:
            x = nag.pop()
            y = nag.pop()
            ans *= max(x * y, a * b)
            ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
mod=10**9+7
P=1
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  P=P*pow(B[0],mod-2,mod)*B[-1]%mod
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break
if Y*V>Z*W:
  print(P*Y*pow(W,mod-2,mod)%mod)
else:
  print(P*Z*pow(V,mod-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()
    ans = 1
    cnt = 0
    l = 0
    r = n-1
    x = bisect.bisect_left(a,0)
    y = bisect.bisect_right(a,0)
    flag = 0
    if n == 1:
        print(a[0]%mod)
        return
    if n == 2:
        if k == 1:
            print((max(a[0],a[1]))%mod)
        else:
            print(a[0]*a[1]%mod)
        return
    if k == n:
        if x%2 == 0:
            flag = 1
    elif k == n-1:
        if x == n:
            if k%2 == 0:
                flag = 1
        else:
            if x%2 == 1:
                flag = 1
            else:
                if x != n:
                    flag = 1
    else:
        if x == n:
            if k%2 == 0:
                flag = 1
        flag = 1
    if flag:
        while True:
            if a[l+1] >= 0:
                ans *= a[r]
                ans %= mod
                cnt += 1
                r -= 1
            else:
                if a[l]*a[l+1] >= a[r]*a[r-1] and cnt < k-1:
                    ans *= a[l]
                    ans *= a[l+1]
                    ans %= mod
                    cnt += 2
                    l += 2
                else:
                    ans *= a[r]
                    ans %= mod
                    cnt += 1
                    r -= 1
            if cnt == k:
                break
        print(ans)
    else:
        for i in range(n):
            a[i] = abs(a[i])
        a.sort()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

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

nums = list(map(int, input().split()))

ans = -9999999
for v in combinations(nums, k):
    prod = np.prod(v)
    ans = max(ans, prod)

print(ans % (10**9+7))

Submission status: Wrong Answer

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

b = [(abs(i), 1 if i >= 0 else -1) for i in a]

b = sorted(b)
b = list(reversed(b))
mod = int(1e9 + 7)

def fp(x,y):
	res=1
	while y > 0:
		if y % 2 == 1:
			res *= x
		x *= x
		y //= 2
		x %= mod
		res %= mod
	return res

def inv(x):
	return fp(x,mod-2)

p = 1
signe = 1
for i in range(k):
	p *= b[i][0]
	p %= mod
	if b[i][0] == 0:
		signe = 0
	signe *= b[i][1]

if signe >= 0:
	print(p % mod)
else:
	# choice between replacing the last positive by the next negative
	# and replacing the last negative by the next positive
	lastP, nextP, lastN, nextN = -1, -1, -1, -1
	for i in range(k):
		if b[i][0] * b[i][1] >= 0:
			lastP = i
		if b[i][0] * b[i][1] <= 0:
			lastN = i
	for i in range(k, n):
		if b[i][0] * b[i][1] >= 0:
			nextP = i
		if b[i][0] * b[i][1] <= 0:
			nextN = i
	if (lastP!=-1 and nextN !=-1) and (lastN!=-1 and nextP!=-1):
		if b[nextN][0] * b[lastN][0] >= b[nextP][0] * b[lastP][0]:
			ans = p * inv(b[lastP][0]) * b[nextN][0]
			ans %= mod
			print(ans)
		else:
			ans = p * inv(b[lastN][0]) * b[nextN][0]
			ans %= mod
			print(ans)
	elif lastP!=-1 and nextN!=-1:
		ans = p * inv(b[lastP][0]) * b[nextN][0]
		ans %= mod
		print(ans)
	elif lastN!=-1 and nextP!=-1:
		ans = p * inv(b[lastN][0]) * b[nextP][0]
		ans %= mod
		print(ans)
	else:
		# tout le monde est negatif
		a = list(reversed(sorted(a)))
		p = 1
		for i in range(k):
			p *= a[i]
			p %= mod
		print(p)