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

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p + 1, m - 1, plus, minus, mod, K)
  elif p == 0:
    main(p + 1, m - 1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus, mod, K)
    else:
      main(p - 1, m + 1, plus, minus, mod, K)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=lambda x: -abs(x))
mod=10**9+7
p=1
mm=0
for i in range(k):
    if a[i]<0:
        mm+=1
    p*=a[i]
    p%=mod
if n==k or mm%2==0:
    print(p)
    exit()
    
m=0
for i in a:
    if i<=0:
        m+=1
if m==n:
    p=1
    for i in range(k):
        p*=a[n-i-1]
        p%=mod
    print(p)
    exit()
b1=[]
b2=[]
for i in range(k):
    if len(b1)==0 and a[k-1-i]>=0:
        b1.append(a[k-1-i])
    if len(b2)==0 and a[k-1-i]<0:
        b2.append(a[k-1-i])
for i in range(n-k):
    if len(b1)==1 and a[k+i]<0:
        b1.append(a[k+i])
    if len(b2)==1 and a[k+i]>=0:
        b2.append(a[k+i])
f=0
if len(b1)==len(b2)==2:
    if b1[1]*b2[0]>=b1[0]*b2[1]:
        f=1
    else:
        f=2
elif len(b2)<2:
    f=1
else:
    f=2

if f==1:
    p*=b1[1]*pow(b1[0],mod-2,mod)
    print(p%mod)
    exit()
else:
    p*=b2[1]*pow(b2[0],mod-2,mod)
    print(p%mod)
    exit()

Solution (Python):
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():

    N, K = map(int, sys.stdin.readline().rstrip().split())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    P, M = [], []
    
    for i in range(N):
        n = A[i]
        if n < 0:
            M.append(n)
        else:
            P.append(n)

    
    P.sort(reverse=True)
    M.sort()
    n_p = len(P)
    n_m = len(M)
    

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

    
    if n_p == 0:
        if K % 2 == 1:  
            ans = 1
            for i in range(K):
                ans = ans * M[-(i + 1)] % MOD
            print(ans)
            return
        else:
            ans = 1
            for i in range(K):
                ans = ans * M[i] % MOD
            print(ans)
            return

    i, j = 0, 0
    if K % 2 == 1:
        i += 1
    
    while K > 1:
        p, m = 0, 0
        if i + 1 < n_p:
            p = P[i] * P[i + 1]
        if j + 1 < n_m:
            m = M[j] * M[j + 1]
        if p >= m:
            i += 2
        else:
            j += 2
        K -= 2

    
    ans = 1
    for u in range(i):
        ans = ans * P[u] % MOD
    for v in range(j):
        ans = ans * M[v] % MOD

    print(ans)


main()

Solution (Python):
def solve():
    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) 
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])
    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & remain_M & exist_m & remain_P:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    else:
        M.pop() 
        m = sorted(M, reverse = True)[:k]
    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):
def solve():
    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) 
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])
    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & exist_m & remain_P & remain_M:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    else:
        M.pop() 
        m = sorted(M, reverse = True)[:k]
    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):
def solve():
    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) 
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])

    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & exist_m & remain_P & remain_M:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    elif k%2:
        M.pop()
        m = sorted(M, reverse = True)[:k]
    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):
def solve():
    if k == n: return P + M

    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) 
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])

    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & exist_m & remain_P & remain_M:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    elif k%2:
        M.pop()
        m = sorted(M, reverse = True)[:k]

    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):
def solve():
    if k==n: return P + M
    if len(M) == n: return sorted(M, reverse=k%2)[:k]

    P.sort(reverse=True)
    M.sort()
    P.append(-1)
    M.append(1) 
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]:
            ma.append(M[len(ma)])
        else:
            pa.append(P[len(pa)])

    if len(ma)%2 == 0: return pa + ma

    exist_pa = len(pa) > 0
    exist_ma = len(ma) > 0
    remain_p = len(P) - 1 > len(pa)
    remain_m = len(M) - 1 > len(ma)
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop()
            ma.append(M[len(ma)])
        else:
            ma.pop()
            pa.append(P[len(pa)])
    elif exist_ma & remain_p:
        ma.pop()
        pa.append(P[len(pa)])
    elif exist_pa & remain_m:
        pa.pop()
        ma.append(M[len(ma)])
    return pa + ma

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():
    if k==n: return A
    if len(M) == n: return sorted(M, reverse=k%2)[:k]

    P.sort(reverse=True)
    M.sort()
    P.append(-1)
    M.append(1) 
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]:
            ma.append(M[len(ma)])
        else:
            pa.append(P[len(pa)])

    if len(ma)%2 == 0: return pa + ma

    exist_pa = len(pa) > 0
    exist_ma = len(ma) > 0
    remain_p = len(P) - 1 > len(pa)
    remain_m = len(M) - 1 > len(ma)
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop()
            ma.append(M[len(ma)])
        else:
            ma.pop()
            pa.append(P[len(pa)])
    elif exist_ma & remain_p:
        ma.pop()
        pa.append(P[len(pa)])
    elif exist_pa & remain_m:
        pa.pop()
        ma.append(M[len(ma)])
    return pa + ma

n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] 
for a in A:
    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):
n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] 
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

def mix():
    len_p = len(P); len_m = len(M)
    P.sort(reverse=True); M.sort()
    P.append(-1); M.append(1) 
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])
    if len(ma)%2 == 0: return pa + ma
    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p > len(pa); remain_m = len_m > len(ma)
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop(); ma.append(M[len(ma)])
        else: ma.pop(); pa.append(P[len(pa)])
    elif exist_ma & remain_p: ma.pop(); pa.append(P[len(pa)])
    elif exist_pa & remain_m: pa.pop(); ma.append(M[len(ma)])
    return pa + ma

ans_list = []
if k==n: ans_list = A

elif len(M) == n: ans_list = sorted(M, reverse=k%2)[:k]
else: ans_list = mix()
MOD = 10**9 + 7
ans = 1
for a in ans_list: ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] 
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

def mix():
    len_p = len(P); len_m = len(M)
    P.sort(reverse=True); M.sort()
    P.append(-1); M.append(1) 
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])
    if len(ma)%2 == 0: return pa + ma
    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p > len(pa); remain_m = len_m > len(ma)
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop(); ma.append(M[len(ma)])
        else: ma.pop(); pa.append(P[len(pa)])
    elif exist_ma & remain_p: ma.pop(); pa.append(P[len(pa)])
    elif exist_pa & remain_m: pa.pop(); ma.append(M[len(ma)])
    return pa + ma

ans_list = []
if k==n: ans_list = A
elif len(P) == n: ans_list = sorted(P, reverse=True)[:k]
elif len(M) == n: ans_list = sorted(M, reverse=k%2)[:k]
else: ans_list = mix()
MOD = 10**9 + 7
ans = 1
for a in ans_list: ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] 
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

def mix():
    len_p = len(P); len_m = len(M)
    P.sort(reverse=True); M.sort()
    P.append(-1); M.append(1) 
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])
    if len(ma)%2 == 0: return pa + ma
    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p > len(pa); remain_m = len_m > len(ma)
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop(); ma.append(M[len(ma)])
        else:
            ma.pop(); pa.append(P[len(pa)])
        return pa + ma
    if exist_ma & remain_p:
        ma.pop(); pa.append(P[len(pa)])
        return pa + ma
    if exist_pa & remain_m:
        pa.pop(); ma.append(M[len(ma)])
        return pa + ma
    return pa + ma

ans_list = []
if k==n: ans_list = A
elif len(P) == n: ans_list = sorted(P, reverse=True)[:k]
elif len(M) == n: ans_list = sorted(M, reverse=k%2)[:k]
else: ans_list = mix()
MOD = 10**9 + 7
ans = 1
for a in ans_list: ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] 
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

def mix():
    len_p = len(P); len_m = len(M)
    P.sort(reverse=True); M.sort()
    P.append(-1); M.append(1) 
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])
    if len(ma)%2 == 0: return pa + ma
    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop(); ma.append(M[len(ma)])
        else:
            ma.pop(); pa.append(P[len(pa)])
    elif exist_ma & remain_p:
        ma.pop(); pa.append(P[len(pa)])
    elif exist_pa & remain_m:
        pa.pop(); ma.append(M[len(ma)])
    else:
        P.pop(); M.pop()
        P.sort(); M.sort(reverse=True)
        P.append(-1); M.append(1) 
        pa, ma = [], []
        while len(pa) + len(ma) < k:
            if P[len(pa)] >= -M[len(ma)]: ma.append(M[len(ma)])
            else: pa.append(P[len(pa)])
        if len(ma)%2 == 1: return pa + ma
        exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
        remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
        if exist_pa & exist_ma & remain_p & remain_m:
            if abs(pa[-1] * P[len(pa)]) >= abs(ma[-1] * M[len(ma)]):
                pa.pop(); ma.append(M[len(ma)])
            else:
                ma.pop(); pa.append(P[len(pa)])
        elif exist_ma & remain_p:
            ma.pop(); pa.append(P[len(pa)])
        elif exist_pa & remain_m:
            pa.pop(); ma.append(M[len(ma)])
    return pa + ma

ans_list = []
if k==n: ans_list = A
elif len(P) == n: ans_list = sorted(P, reverse=True)[:k]
elif len(M) == n: ans_list = sorted(M, reverse=k%2)[:k]
else: ans_list = mix()
MOD = 10**9 + 7
ans = 1
for a in ans_list: ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Solution (Python):
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

MOD = 10**9 + 7
INF = MOD
def mmul(a, b): return a*b%MOD

n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] 
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

debug('A {}'.format(sorted(A, reverse=True, key=lambda x:abs(x))))


def mix():
    len_p = len(P); len_m = len(M)

    P.sort(reverse=True); M.sort()
    P.append(-1); M.append( 1) 

    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))
    if len(ma)%2 == 0: return pa + ma

    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    debug('exist_pa {}'.format(exist_pa));debug('exist_ma {}'.format(exist_ma))
    debug('remain_p {}'.format(remain_p));debug('remain_m {}'.format(remain_m))

    if exist_pa & exist_ma & remain_p & remain_m:
        p_in = pa[-1]; p_out = P[len(pa)]
        m_in = ma[-1]; m_out = M[len(ma)]
        if abs(p_in*p_out) < abs(m_in*m_out): pa.pop(); ma.append(m_out)
        else: ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    
    
    if exist_ma & remain_p:
        m_in = ma[-1]; p_out = P[len(pa)]
        ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    
    
    if exist_pa & remain_m:
        p_in = pa[-1]; m_out = M[len(ma)]
        pa.pop(); ma.append(m_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    
    P.pop(); M.pop()

    P.sort(); M.sort(reverse=True)
    P.append(-1); M.append( 1) 
    debug('---')
    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] >= -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))
    if len(ma)%2 == 1: return pa + ma

    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    debug('exist_pa {}'.format(exist_pa));debug('exist_ma {}'.format(exist_ma))
    debug('remain_p {}'.format(remain_p));debug('remain_m {}'.format(remain_m))

    if exist_pa & exist_ma & remain_p & remain_m:
        p_in = pa[-1]; p_out = P[len(pa)]
        m_in = ma[-1]; m_out = M[len(ma)]
        if abs(p_in*p_out) >= abs(m_in*m_out): pa.pop(); ma.append(m_out)
        else: ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    
    if exist_ma & remain_p:
        m_in = ma[-1]; p_out = P[len(pa)]
        ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    
    if exist_pa & remain_m:
        p_in = pa[-1]; m_out = M[len(ma)]
        pa.pop(); ma.append(m_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    
    return pa + ma


ans = 1
if k==n:
    debug('k==n: {} == {} '.format(k,n))
    debug('A {}'.format(A))
    for a in A: ans = mmul(ans, a)
else:
    debug('k<n: {} < {} '.format(k,n))
    if len(P) == n:
        debug('n({}) all plus({})'.format(n,len(P)))
        P.sort(reverse=True)
        debug('P[:k] {}'.format(P[:k]))
        for a in P[:k]: ans = mmul(ans, a)
    elif len(M) == n:
        debug('n({}) all minus({})'.format(n,len(M)))
        if k%2:
            debug('k({}) is odd ({})'.format(k,k%2))
            M.sort(reverse=True)
        else:
            debug('k({}) is even ({})'.format(k,k%2))
            M.sort()
        debug('M[:k] {}'.format(M[:k]))
        for a in M[:k]: ans = mmul(ans, a)
    else:
        debug('n({}) mix plus({}):minus({})'.format(n,len(P),len(M)))
        for a in mix(): ans = mmul(ans, a)

ans += MOD; ans %= MOD
debug('ans {}'.format(ans))
print(ans)

Solution (Python):
from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
elif N==K:
    print(mat(A))
else:
    negative_all = np.where(A_pn)[0]
    negative_rest = np.count_nonzero(negative_all>=K)
    if negative_rest == 0:
        
        A[negative_all[-1]] = A[K]
        print(mat(A[:K]))
    elif negative_rest == N-K:
        
        last_positive = np.where(A_pn[:K]==False)[0][-1]
        A[last_positive] = A[K]
        print(mat(A[:K]))
    elif len(negative_all)-negative_rest==K:
        
        last_negative = negative_all[negative_all<K][-1]
        next_positive = np.where(A_pn==False)[0][0]
        A[last_negative] = A[next_positive]
        print(mat(A[:K]))
    else:
        last_negative = negative_all[negative_all<K][-1]
        next_negative = negative_all[negative_all>=K][0]
        positive_all = np.where(A_pn==False)[0]
        last_positive = positive_all[positive_all<K][-1]
        next_positive = positive_all[positive_all>=K][0]
        if A[last_negative]*A[next_negative] > A[last_positive]*A[next_positive]:
            A[last_positive] = A[next_negative]
        else:
            A[last_negative] = A[next_positive]
        print(mat(A[:K]))

Solution (Python):

import sys
input = sys.stdin.readline


def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    

def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp


def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);


def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 


def upper_bound(a, x, lo=0, hi = None):
    if hi == None:
        hi = len(a);
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo


def primefs(n):
    
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    
    
    return primes


def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 


def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b









def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;




def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x


def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime


MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    




def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    
    


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

def str_array():
    return input().strip().split();


MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');



mod = 1000000007
N, K = int_array(); A = int_array();
pos = []; neg = [];
for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    else:
        neg.append(A[i])

ans = 1
if len(pos) == 0:
    if K % 2 == 0:
        neg.sort(reverse=True)
    else:
        neg.sort()
    for i in range(K):
        ans = (ans * neg.pop()) % mod
elif N == K:
    for i in pos:
        ans = (ans * i) % mod
    for i in neg:
        ans = (ans * i) % mod
else:
    pos.sort();
    neg.sort(reverse=True)
    if K % 2 == 1:
        ans = pos.pop()
    for i in range(K//2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
                for _ in range(2):
                    ans = ans * pos.pop() % mod
            else:
                for _ in range(2):
                    ans = ans * neg.pop() % mod
        elif len(pos) > 1:
            for _ in range(2):
                ans = ans * pos.pop() % mod
        else:
            for _ in range(2):
                ans = ans * neg.pop() % mod

print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus=[]
plus=[]
cnt=Counter(a)
zerocnt=cnt[0]
minuscnt=0
pluscnt=0
for i in range(n):
    if a[i]<0:
        minuscnt+=1
        minus.append(a[i])
    elif a[i]>0:
        pluscnt+=1
        plus.append(a[i])


if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans%mod)
    quit()

if minuscnt==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=a[i]
            ans%=mod
        print(ans)
    else:
        for i in range(k):
            ans*=a[-1-i]
            ans%=mod
        print(ans)
    quit()

if minuscnt%2==1:
    minuscnt-=1


plus.reverse()




ans=1
nokori=k
m,p=0,0


while nokori:
    
    if m==minuscnt:
        if p!=pluscnt:
            ans*=plus[p]
            p+=1
            nokori-=1
        else:
            ans=0
            nokori=0
    elif p==pluscnt:
        if nokori==1:
            ans=0
            nokori-=1
        else:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
    elif p+1==pluscnt:
        if nokori%2==0:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
            
        else:
            ans*=plus[p]
            p+=1
            nokori-=1
            
            
            
            
            
            
            
            
    elif nokori==1:
        ans*=plus[p]
        nokori-=1
    elif plus[p]*plus[p+1]>minus[m]*minus[m+1]:
        
        
        
        
        
        ans*=plus[p]
        p+=1
        nokori-=1
    else:
        ans*=minus[m]*minus[m+1]
        m+=2
        nokori-=2
    ans%=mod
print(ans%mod)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
mod=10**9+7
l=0
r=n-1
ans=1
if k%2==1:
  ans=a[0]
  l=1
if ans<0:
  c=1
  for i in range(k):
    c=c*a[i]%mod
  print(c)
  
else:
  for i in range(k//2):
    L=a[l]*a[l+1]
    R=a[r]*a[r-1]
    if L>=R:
      ans=ans*L%mod
      l+=2
    else:
      ans=ans*R%mod
      r-=2
  print(ans)

Solution (Python):
import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
    elif a < 0:
        A2.append(-a)
    else:
        zero += 1

B1 = np.log(np.array(A1, dtype=np.longdouble))
B2 = np.log(np.array(A2, dtype=np.longdouble))
A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = np.insert(B1.cumsum(), 0, 0)
accrev1 = np.insert(B1[::-1].cumsum(), 0, 0)
acc2 = np.insert(B2.cumsum(), 0, 0)
accrev2 = np.insert(B2[::-1].cumsum(), 0, 0)
mx = -np.inf
mn = np.inf
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -np.inf:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)