Problem p02616 (python)

Fixed submission:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

elif all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg: break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg: break

        # print(used)
        # print(used_min_pos)
        # print(used_min_neg)
        # print(rest)
        # print(rest_min_pos)
        # print(rest_min_neg)

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest[rest_min_pos]
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest[rest_min_neg]
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_pos])
            v2 = abs(used[used_min_neg] * rest[rest_min_neg])
            if v1 > v2:
                used[used_min_neg] = rest[rest_min_pos]
            else:
                used[used_min_pos] = rest[rest_min_neg]

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

elif all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg: break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg: break

        # print(used)
        # print(used_min_pos)
        # print(used_min_neg)
        # print(rest)
        # print(rest_min_pos)
        # print(rest_min_neg)

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest[rest_min_pos]
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest[rest_min_neg]
        else:
            v1 = abs(used[used_min_pos] / rest[rest_min_neg])
            v2 = abs(used[used_min_neg] / rest[rest_min_pos])
            if v1 > v2:
                used[used_min_pos] = rest[rest_min_neg]
            else:
                used[used_min_neg] = rest[rest_min_pos]

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

if all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg:
                break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K-1, -1, -1):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg:
                break

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest_min_pos
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest_min_neg
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_neg])
            v2 = abs(used[used_min_neg] * rest[rest_min_pos])
            if v1 < v2:
                used[used_min_pos] = rest_min_neg
            else:
                used[used_min_neg] = rest_min_pos

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))
ans = int(input().strip())

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

if all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg:
                break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K-1, -1, -1):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg:
                break

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest_min_pos
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest_min_neg
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_neg])
            v2 = abs(used[used_min_neg] * rest[rest_min_pos])
            if v1 < v2:
                used[used_min_pos] = rest_min_neg
            else:
                used[used_min_neg] = rest_min_pos

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D
    print(r)
    exit()

if all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

if K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

if K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used[k] >= 0 and used_min_pos is None: used_min_pos = k
            elif used[k] <  0 and used_min_neg is None: used_min_neg = k
            if used_min_pos and used_min_neg:
                break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K, -1, -1):
            if   rest[k] >= 0 and rest_min_pos is None: rest_min_pos = k
            elif rest[k] <  0 and rest_min_neg is None: rest_min_neg = k
            if rest_min_pos and rest_min_neg:
                break

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest_min_pos
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest_min_neg
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_neg])
            v2 = abs(used[used_min_neg] * rest[rest_min_pos])
            if v1 < v2:
                used[used_min_pos] = rest_min_neg
            else:
                used[used_min_neg] = rest_min_pos

    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()


##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [ x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = HeapQueue(As, "max")
    for k in range(K):
        a = As.pop()
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = [a for a in As if a >= 0]
    Qs = [a for a in As if a <= 0]

    Ps = HeapQueue(Ps, "max")
    Qs = HeapQueue(Qs, "min")

    while k < K:
    
        if len(Ps) == len(Qs) == 0:
            print(0)
            exit()

        elif (K - k) == 1:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        elif len(Ps) == 0:
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            r = (r * q) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        else:
            p1 = Ps.pop()
            p2 = Ps.pop()
            p  = p1 * p2
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            if p > q:
                r = (r * p1) % D
                Ps.push(p2)
                Qs.push(q1)
                Qs.push(q2)
                k += 1
            else:
                r = (r * q) % D
                Ps.push(p1)
                Ps.push(p2)
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [ x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = HeapQueue(As, "max")
    for k in range(K):
        a = As.pop()
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = [a for a in As if a >= 0]
    Qs = [a for a in As if a < 0]

    Ps = HeapQueue(Ps, "max")
    Qs = HeapQueue(Qs, "min")

    while k < K:
    
        if len(Ps) == len(Qs) == 0:
            print(0)
            exit()

        elif (K - k) == 1:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        elif len(Ps) == 0:
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            r = (r * q) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        else:
            p1 = Ps.pop()
            p2 = Ps.pop()
            p  = p1 * p2
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            if p > q:
                r = (r * p1) % D
                Ps.push(p2)
                Qs.push(q1)
                Qs.push(q2)
                k += 1
            else:
                r = (r * q) % D
                Ps.push(p1)
                Ps.push(p2)
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [ x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = HeapQueue(As, "max")
    for k in range(K):
        a = As.pop()
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = [a for a in As if a > 0]
    Qs = [a for a in As if a < 0]

    Ps = HeapQueue(Ps, "max")
    Qs = HeapQueue(Qs, "min")

    while k < K:
    
        if len(Ps) == len(Qs) == 0:
            print(0)
            exit()

        elif len(Ps) == 0:
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            r = (r * (q % D)) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop()
            r = (r * (p % D)) % D
            k += 1

        else:
            p1 = Ps.pop()
            p2 = Ps.pop()
            p  = p1 * p2
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            if p > q:
                r = (r * (p1 % D)) % D
                Ps.push(p2)
                Qs.push(q1)
                Qs.push(q2)
                k += 1
            else:
                r = (r * (q % D)) % D
                Ps.push(p1)
                Ps.push(p2)
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = sorted([a for a in As if a > 0], reverse=True)
    Qs = sorted([a for a in As if a < 0])

    while k < K:
    
        if len(Ps) == len(Qs) == 0:
            print(0)
            exit()

        elif len(Ps) == 0:
            q1 = Qs.pop(0)
            q2 = Qs.pop(0)
            q  = q1 * q2
            r = (r * (q % D)) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop(0)
            r = (r * (p % D)) % D
            k += 1

        else:
            p1 = Ps.pop(0)
            p2 = Ps.pop(0)
            p  = p1 * p2
            q1 = Qs.pop(0)
            q2 = Qs.pop(0)
            q  = q1 * q2
            if p > q:
                r = (r * (p1 % D)) % D
                Ps = [p2] + Ps
                Qs = [q1, q2] + Qs
                k += 1
            else:
                r = (r * (q % D)) % D
                Ps = [p1, p2] + Ps
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

Ps = [-a for a in As if a > 0]
Qs = [a for a in As if a < 0]
Zs = [ 0 for a in As if a == 0]
D  = int(1E9 + 7)

if len(Ps) == 0 and K % 2 == 1:
    Qs = [- a for a in As if a < 0]
    r = 1
    for k in range(K):
        q = - heapq.heappop(Qs)
        r = (r * q % D) % D
    print(r)
    exit()


heapq.heapify(Ps)
heapq.heapify(Qs)


k = 0
r = 1

while k < K:

    if len(Ps) == 0 and len(Qs) == 0:
        k = 0
        break

    if (K - k) == 1 and len(Ps) > 0:
        p = - heapq.heappop(Ps)
        r = (r * (p % D)) % D
        k += 1

    elif (K - k) == 1 and len(Qs) > 0:
        q = - heapq.heappop(Qs)
        r = (r * (q % D)) % D
        k += 1

    elif len(Qs) < 2:
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2
        r  = (r * (p % D)) % D
        k += 2

    elif len(Ps) < 2:
        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2
        r  = (r * (q % D)) % D
        k += 2

    else: 
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2

        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2

        if p > q:
            r  = (r * (p % D)) % D
            heapq.heappush(Qs, -q1)
            heapq.heappush(Qs, -q2)
        else:
            r  = (r * (q % D)) % D
            heapq.heappush(Ps, -p1)
            heapq.heappush(Ps, -p2)

        k += 2

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

Ps = [-a for a in As if a > 0]
Qs = [a for a in As if a < 0]
Zs = [ 0 for a in As if a == 0]
D  = int(1E9 + 7)

if len(Ps) == 0 and K % 2 == 1:
    Qs = [- a for a in As if a < 0]
    r = 1
    for k in range(K):
        q = - heapq.heappop(Qs)
        print(q)
        r = (r * q % D) % D
    print(r)
    exit()


heapq.heapify(Ps)
heapq.heapify(Qs)


k = 0
r = 1

while k < K:

    if len(Ps) == 0 and len(Qs) == 0:
        k = 0
        break

    if (K - k) == 1 and len(Ps) > 0:
        p = - heapq.heappop(Ps)
        r = (r * (p % D)) % D
        k += 1

    elif (K - k) == 1 and len(Qs) > 0:
        q = - heapq.heappop(Qs)
        r = (r * (q % D)) % D
        k += 1

    elif len(Qs) < 2:
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2
        r  = (r * (p % D)) % D
        k += 2

    elif len(Ps) < 2:
        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2
        r  = (r * (q % D)) % D
        k += 2

    else: 
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2

        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2

        if p > q:
            r  = (r * (p % D)) % D
            heapq.heappush(Qs, -q1)
            heapq.heappush(Qs, -q2)
        else:
            r  = (r * (q % D)) % D
            heapq.heappush(Ps, -p1)
            heapq.heappush(Ps, -p2)

        k += 2

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

Ps = [-a for a in As if a > 0]
Qs = [a for a in As if a < 0]
Zs = [ 0 for a in As if a == 0]
D  = int(1E9 + 7)

heapq.heapify(Ps)
heapq.heapify(Qs)

k = 0
r = 1

while k < K:

    if len(Ps) == 0 and len(Qs) == 0:
        k = 0
        break

    if (K - k) == 1:
        p = - heapq.heappop(Ps)
        r = (r * (p % D)) % D
        k += 1

    elif len(Qs) < 2:
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2
        r  = (r * (p % D)) % D
        k += 2

    else: 
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2

        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2

        if p > q:
            r  = (r * (p % D)) % D
            heapq.heappush(Qs, -q1)
            heapq.heappush(Qs, -q2)
        else:
            r  = (r * (q % D)) % D
            heapq.heappush(Ps, -p1)
            heapq.heappush(Ps, -p2)

        k += 2

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker