Problem p02616 (python)

Fixed submission:
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
    else: minus = False
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus and K != N:
    non_neg, neg = None, None
    for a in A[K:]:
        if a >= 0 and non_neg is None: non_neg = a
        elif a < 0 and neg is None: neg = a
        if non_neg is not None and neg is not None: break
    if non_neg is None:
        if last_plus:
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
    elif neg is None:
        ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
    else:
        if last_plus and abs(last_plus * non_neg) < abs(last_minus * neg):
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
    else: minus = False
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus and K != N:
    non_neg, neg = None, None
    for a in A[K:]:
        if a >= 0 and non_neg is None: non_neg = a
        elif a < 0 and neg is None: neg = a
        if non_neg is not None and neg is not None: break
    if non_neg is None:
        if last_plus:
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
    elif neg is None:
        ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
    else:
        if abs(last_plus * non_neg) < abs(last_minus * neg):
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus:
    ans *= modular_inverse(last_minus, MOD)
    ans %= MOD
    for a in A[K:]:
        if a >= 0: ans *= a; ans %= MOD; break
    else:
        if last_plus is not None:
            ans *= last_minus * modular_inverse(last_plus, MOD) * A[K]
            ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
print(ans)