Problem p02616 (python)

Fixed submission:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        if max(a) <= 0:
            ans = 1
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
            print(ans)
        else:
            A = min(a[k:])
            B = max(a[k:])
            if A >= 0:
                ans *= pow(L, mod - 2, mod)
                ans *= B
            else:
                if A * L > B * R:
                    ans *= pow(R, mod - 2, mod)
                    ans *= A
                else:
                    ans *= pow(L, mod - 2, mod)
                    ans *= B
            print(ans % mod)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
    else:
        if max(a) <= 0:
            ans = 1
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
            print(ans)
            return
        else:
            print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
        
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    t = 0
    L = 0
    R= 0
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if t:
        if len(a) >= k:
            A = min(a[k:])
            B = max(a[k:])
            if A >= 0:
                ans *= pow(L, mod - 2, mod)
                ans *= B
            else:
                if A * L > B * R:
                    ans *= pow(R, mod - 2, mod)
                    ans *= A
                else:
                    ans *= pow(L, mod - 2, mod)
                    ans *= B
            print(ans%mod)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    X = []
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    while len(mi) >= 2:
        xx = heappop(mi)
        xy = heappop(mi)
        X.append(xx * xy)
    while len(ma) >= 2:
        xx = -heappop(ma)
        xy = -heappop(ma)
        X.append(xx * xy)
    X.sort()
    ans = 1
    t = 0
    while X:
        ans *= X.pop()
        ans %= mod
        t += 2
        if t >= k - 1: break
    if t == k:
        print(ans)
    else:
        ans *= - heappop(ma)
        ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    X = []
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    while len(mi) >= 2:
        xx = heappop(mi)
        xy = heappop(mi)
        X.append(xx * xy)
    while len(ma) >= 2:
        xx = -heappop(ma)
        xy = -heappop(ma)
        X.append(xx * xy)
    X.sort()
    ans = 1
    for i in range(k // 2):
        ans *= X.pop()
        ans %= mod
    if k & 1:
        ans *= - heappop(ma)
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        return
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        X = k - L
        if len(mi) & 1:
            L -= 1
            X -= 1
            ans *= -heappop(ma)
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        X = k - L
        if len(mi) & 1:
            L -= 1
            X -= 1
            ans *= -heappop(ma)
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - L
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 <= h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - len(mi)
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 <= h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 <= h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - len(mi)
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 <= h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()