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: Runtime Error

Solution code:
#!/usr/bin/python3
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:]))
elif any(x > 0 for x in a[:n-k]):
    rem = next(i for i, x in enumerate(a[-k:]) if x < 0)
    print(next(x for x in reversed(a[:n-k]) if x > 0) * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != rem), default=1) % M)
else:
    print(reduce(modmul, a[:k]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
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 = [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:]))
elif any(x > 0 for x in a[:n-k]):
    rem = next(i for i, x in enumerate(a[-k:]) if x < 0)
    print(next(x for x in reversed(a[:n-k]) if x > 0) * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != rem), default=1) % M)
else:
    print(reduce(modmul, a[:k]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
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 = [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:]))
elif any(x > 0 for x in a[:n-k]):
    rem = next(i for i, x in enumerate(a[-k:]) if x < 0)
    print(next(x for x in a[:n-k] if x > 0) * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != rem)) % M)
else:
    print(reduce(modmul, a[:k]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
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 = [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:]) % M)
elif any(x > 0 for x in a[:n-k]):
    rem = next(i for i, x in enumerate(a[-k:]) if x < 0)
    print(next(x for x in a[:n-k] if x > 0) * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != rem) % M))
else:
    print(reduce(modmul, a[:k]))

Submission status: Runtime Error

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


def solve(N, K, A):
    ans = 1
    if N == K:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        A_nonneg = [a for a in A if a >= 0]
        A_neg = [a for a in A if a < 0]
        A_nonneg.sort()
        A_neg.sort(reverse=True)
        count = 0
        while count < K:
            if count == K - 1 or len(A_neg) < 2 or A_nonneg[-1] > A_neg[-1] * A_neg[-2]:
                count += 1
                ans *= A_nonneg.pop()
            else:
                count += 2
                ans *= A_neg.pop()
                ans *= A_neg.pop()
            ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Runtime Error

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


def solve(N, K, A):
    ans = 1
    if N == K:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        A_nonneg = [a for a in A if a >= 0]
        A_neg = [a for a in A if a < 0]
        A_nonneg.sort()
        A_neg.sort(reverse=True)
        count = 0
        while count < K:
            if count == K - 1 or A_nonneg[-1] > A_neg[-1] * A_neg[-2]:
                count += 1
                ans *= A_nonneg.pop()
            else:
                count += 2
                ans *= A_neg.pop()
                ans *= A_neg.pop()
            ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A_abs = []
plus_queue = []
minus_queue = []
mul = 1
minus = 0

for i in range(N):
  A_max = max(abs(A[0]), abs(A[-1]))
  if A_max == abs(A[-1]) and A[-1] != 0:
    app = A.pop(-1)
    A_abs.append(app)
    if app > 0:
      plus_queue.append(app)
    else:
      minus_queue.append(app)
  elif A_max == abs(A[0]):
    app = A.pop(0)
    A_abs.append(app)
    if app < 0:
      minus_queue.append(app)
    else:
      plus_queue.append(app)
    
if K > 1 and plus_queue != []:
  i = 0
  while i < K-2:
    abs_pop = A_abs.pop(0)
    if abs_pop > 0:
      mul = mul * plus_queue.pop(0) % (10**9+7)
      i += 1
    else:
      minus += 1
      if minus%2 == 0:
        for o in range(2):
          mul = mul * minus_queue.pop(0) % (10**9+7)
        i += 2

  if i == K-1:
    if len(plus_queue) > 0:
      mul = mul *  plus_queue[0] % (10**9+7)
    else:
      mul = mul * minus_queue[0] % (10**9+7)

  else:
    if len(plus_queue) > 1 and len(minus_queue) > 1:
      plus_mul = plus_queue[0] * plus_queue[1]
      minus_mul = minus_queue[0] * minus_queue[1]
      max_mul = max(plus_mul, minus_mul)
    elif len(plus_queue) > 1:
      max_mul = plus_queue[0] * plus_queue[1]
    elif len(minus_queue) > 1:
      max_mul = minus_queue[0] * minus_queue[1]
    else:
      max_mul = plus_queue[0] * minus_queue[0]
    mul = mul * (max_mul % (10**9+7)) % (10**9+7)

elif len(A_abs) >= K and K > 1:
  for i in range(K):
    mul = mul * minus_queue[-(i+1)] % (10**9+7)

elif len(A_abs) >= K and K == 1:
  if len(plus_queue) > 0:
    mul = plus_queue[0] % (10**9+7)
  else:
    mul = minus_queue[-1] % (10**9+7)
else:
  mul = 0

print(mul)

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 正の数が存在しないかつk:奇数のとき
if (len(plist) == 0 and k % 2 == 1):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = (MOD - rem) % MOD
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, ((k - len(plist) + 1) // 2))  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] < plist[k - 2 * i - 1] * plist[k - 2 * i - 2]:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 1

print(int(rem))

Submission status: Runtime Error

Solution code:
import copy
N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

B = sorted(A, key=lambda x: abs(x), reverse=True)

score = 1
x = 0
y = 0
for j in range(K):
    score *= B[j]
    if B[j] > 0:
        x = B[j]
    elif B[j] < 0:
        y = B[j]

if score < 0 and (not N == K):
    C = copy.deepcopy(B[K:N])
    C = sorted(C)

    scoreX = 0
    scoreY = 0
    if (not x == 0) and C[0] < 0:
        scoreY = score / x * C[0] * (-1)
    if (not y == 0) and C[N-K-1] > 0:
        scoreX = score / y * C[N-K-1]

    if scoreX > 0 or scoreY > 0:
        score = max(scoreX,scoreY)
    else:
        score = 1
        for j in range(N-K,N):
            score *= B[j]

print(int(score % (10**9 + 7)))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
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)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    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)) % mod
        	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()

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
pls=[]
mls=[]
for i in range(N):
  if ls[i]>=0:
    pls.append(ls[i])
  else:
    mls.append(ls[i])
pls=sorted(pls)
mls=sorted(mls,reverse=True)

#N=Kのときは全部かけるしかない
if N==K:
  ans=1
  for i in range(N):
    ans=(ans*ls[i])%MOD
  print(ans)
  exit()
  
#全部負の数でKが奇数のとき
if pls==[] and K%2==1:
  ans=1
  for i in range(K):
    ans=(ans*mls[-1-i])%MOD
  print(ans)
  exit()

#その他
p=len(pls)
m=len(mls)
ans=1
k=K
if k%2==1:
  ans=ans*pls[-1]%MOD
  del pls[-1]
  k-=1
while k>0:
  if m==1:
    ans=(ans*pls[-1]*pls[-2])%MOD
    del pls[-1]
    del pls[-1]
    p-=2
  elif p>1 and pls[-1]*pls[-2]>mls[-1]*mls[-2]:
    ans=(ans*pls[-1]*pls[-2])%MOD
    del pls[-1]
    del pls[-1]
    p-=2
  else:
    ans=(ans*mls[-1]*mls[-2])%MOD
    del mls[-1]
    del mls[-1]
    m-=2
  k-=2
print(ans)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
pls=[]
mls=[]
for i in range(N):
  if ls[i]>=0:
    pls.append(ls[i])
  else:
    mls.append(ls[i])
pls=sorted(pls)
mls=sorted(mls,reverse=True)

#N=Kのときは全部かけるしかない
if N==K:
  ans=1
  for i in range(N):
    ans=(ans*ls[i])%MOD
  print(ans)
  exit()
  
#全部負の数でKが奇数のとき
if pls==[] and K%2==1:
  ans=1
  for i in range(K):
    ans=(ans*mls[-1-i])%MOD
  print(ans)
  exit()

#その他
p=len(pls)
m=len(mls)
ans=1
k=K
if k%2==1:
  ans=ans*pls[-1]%MOD
  del pls[-1]
  k-=1
while k>0:
  if m==1:
    ans=(ans*pls[-1]*pls[-2])%MOD
    del pls[-1]
    del pls[-1]
  elif p>1 and pls[-1]*pls[-2]>mls[-1]*mls[-2]:
    ans=(ans*pls[-1]*pls[-2])%MOD
    del pls[-1]
    del pls[-1]
  else:
    ans=(ans*mls[-1]*mls[-2])%MOD
    del mls[-1]
    del mls[-1]
  k-=2
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
values = [int(s) for s in input().split()]
values_abs = {}
for v in values:
  values_abs.setdefault(v, abs(v))
val_sorted = [v for v, x in sorted(values_abs.items(), key=lambda x:x[1], reverse=True)]
all_minus = 1
for v in val_sorted:
  if v > 0:
    all_minus = 0

ans = 1
if all_minus == 1:
  rev = sorted(val_sorted, reverse=True)
  for i in range(K):
    ans = ans * rev[i]
  rest = ans % (1000000000 + 7)
  print(rest)
  exit()
    
plus = []
minus = []
for i in range(K):
  ans = ans * val_sorted[i]
  if val_sorted[i] < 0:
    minus.append(val_sorted[i])
  else:
    plus.append(val_sorted[i])
if ans > 0:
  rest = ans % (1000000000 + 7)
  print(rest)
  exit()
else:  
  next_plus = 'none'
  next_minus = 'none'
  for i in range(K, N):
    if not next_plus == 'none' and not next_minus == 'none':
      break
    if val_sorted[i] > 0:
      if next_plus == 'none':
        next_plus = val_sorted[i]
    else:
      if next_minus == 'none':
        next_minus = val_sorted[i]
        
  cand1 = 1
  for v in plus:
    cand1 = cand1 * v
  if len(minus) > 1:
    for v in minus[0:-1]:
      cand1 = cand1 * v
  else:
    pass
  if next_plus == 'none':
    cand1 = 0
  else:
    cand1 = cand1 * next_plus
  
  cand2 = 1
  if len(plus) > 1:    
    for v in plus[0:-1]:
      cand2 = cand2 * v
  else:
    pass
  for v in minus:
    cand2 = cand2 * v
  if next_minus == 'none':
    cand2 = 0
  else:    
    cand2 = cand2 * next_minus
  
  if cand1 > cand2:
    rest = ans % (1000000000 + 7)
    print(rest)
    exit()
  else:
    rest = ans % (1000000000 + 7)
    print(rest)
    exit()

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 正の数が存在しないかつk:奇数のとき
if (len(plist) == 0 and k % 2 == 1):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = (MOD - rem) % MOD
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, ((k - len(plist) + 1) // 2))  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    print(p, rem)
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] < plist[k - 2 * i - 1] * plist[k - 2 * i - 2]:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 1

print(int(rem))

Submission status: Runtime Error

Solution code:
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 a in minus[N-K:]:
                ans *= a
                ans %= MOD
        else:
            for a in minus[:K]:
                ans *= a
                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:
            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()

Submission status: Runtime Error

Solution code:
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:
        for a in minus[N-K:]:
            ans *= a
            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:
            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()

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 正の数が存在しないかつk:奇数のとき
if (len(plist) == 0 and k % 2 == 1):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = (MOD - rem) % MOD
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, ((k - len(plist) + 1) // 2))  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 1

print(int(rem))

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 正の数が存在しないかつk:奇数のとき
if (len(plist) == 0 and k % 2 == 1):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = (MOD - rem) % MOD
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, ((k - len(plist) + 1) // 2))  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 2

print(int(rem))

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 正の数が存在しないかつk:奇数のとき
if (len(plist) == 0 and k % 2 == 1):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = MOD - rem
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, (k - len(plist)) // 2)  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 2

print(int(rem))

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 全部負の数のとき
if (len(plist) == 0):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = MOD - rem
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, (k - len(plist)) // 2)  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 2

print(int(rem))

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)

rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 全部負の数のとき
if (len(mlist) == n):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = MOD - rem
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, (k - len(plist)) // 2)  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 2

print(int(rem))

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)

rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 全部負の数のとき
if (len(mlist) == n):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = MOD - rem
    else:
        rem = 0
    print(int(rem))
    exit()

i = max(0, (k - len(plist)) // 2)  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 2

print(int(rem))

Submission status: Runtime Error

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
for a in alist:
    if a < 0:
        mlist.append(-a)
    else:
        plist.append(a)
plist.sort(reverse=True)
mlist.sort(reverse=True)

rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    rem = 1
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 全部負の数のとき
if (len(mlist) == n):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    print(int(MOD - rem))
    exit()

i = max(0, (k - len(plist)) // 2)  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist):
    if mlist[(2 * i)] * mlist[(2 * i) + 1] / plist[k - 2 * i - 1] / plist[k - 2 * i - 2] < 1:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 2

print(int(rem))